Welcome to the module on Parallel Sort by Regular Sampling

Parallel sorting by regular sampling (PSRS) was introduced by Li, Lu, Schaeffer, Schillington, Wong and Shi in On the versatility of parallel sorting by regular sampling (Parallel Computing, Volume 19, Issue 10, October 1993, 1079-1103). Read the Abstract of this paper.

Module Prerequisites

To use this module successfully it is important to understand the sequential algorithms partition, quicksort and merge. Information on both of these algorithms can be found in any introductory undergraduate textbook on algorithms.

In this module PSRS will be discussed and presented in an algorithmic manner, and it will be completely implemented as a working program using C++ with MPI (Message Passing Interface). It is assumed that the reader is rather familiar with C++ and is somewhat familiar with MPI. There will be discussion about the MPI function calls. You are encouraged to read the on-line documentation on the template function merge() and on the function qsort(). These are the C++ implementations of quicksort and merge.

Questions

  1. According to the Abstact of the Li et al paper, what are three desirable properties possessed by this algorithm. Make sure you understand those three properties.
  2. Using a list of \(10\) integers, and using the third value as a pivot element, partition the list. What would be the two sublists that quicksort would focus on next?
  3. What is the time complexity of quicksort? Assuming each pivot is ideal give an intuitive justification. What is the space complexity of quicksort? Justify.
  4. What is the purpose of the fourth parameter in cstdlib::qsort()?
  5. Merge two sorted lists of \(5\) integers into a sorted list of \(10\) integers.
  6. What is the time complexity of merge? Justify. What can you say about the space complexity?
  7. In the example given for algorithm::merge() the two inputs are arrays and the output is a vector. How can this be done if the output is an array instead of a vector?
  8. Search for a definition of regular sampling. What is the regular part all about?

Module Organization

The module will be presented in three chapters and three appendices. The first chapter discusses the motivation for the PSRS algorithm, and show it in an algorithmic fashion. The second chapter will present a working C++ with MPI program to implement the algorithm. The last chapter will discuss the overall complexity of the algorithm. There are exercises included with each section. The first appendix presents the multimerge algorithm and provides C++ source code that implements it. The second appendix includes a number of simple but very helpful functions that can be used for run time debugging and testing. The third appendix focuses on two sets of measurements for the execution of PSRS in two different computer architectures.