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.

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*.

- 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.
- 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? - What is the time complexity of
*quicksort*? Assuming each pivot is*ideal*give an intuitive justification. What is the space complexity of*quicksort*? Justify. - What is the purpose of the fourth parameter in
*cstdlib::qsort()*? *Merge*two sorted lists of \(5\) integers into a sorted list of \(10\) integers.- What is the time complexity of
*merge*? Justify. What can you say about the space complexity? - 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? - Search for a definition of
*regular sampling*. What is the*regular*part all about?

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.