.. Parallel Sort by Regular Sampling documentation master file, created by
sphinx-quickstart on Thu Aug 22 18:45:06 2013.
You can adapt this file completely to your liking, but it should at least
contain the root `toctree` directive.
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.
.. index::
single: quick sort
see: quicksort; quick sort
single: merge
single: partition
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*.
.. index::
single: space complexity
single: time complexity
single: pivot
single: regular
single: regular sampling
Questions
---------
#. 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 :math:`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 :math:`5` integers into a sorted list of :math:`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?
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.
Module contents
---------------
.. toctree::
:maxdepth: 2
PSRSalgorithm
PSRSimplementation
PSRSanalysis
PSRSAppendixI
PSRSAppendixII
PSRSAppendixIII