Structured Parallel Programming

Chapter 14

Sample Sort

The sample sort example demonstrates a partitioning-based sort that overcomes the scaling limitation of Quicksort described in Section 8.9.3, which arose because Quicksort’s partitioning operation is serial. Sample sort overcomes this deficiency by parallelizing partitioning. The key patterns in the example are binning and packing of data in parallel. Note that what we have defined as the partition pattern just provides a different view of data, whereas what is commonly meant in the description of sorting algorithms by “partitioning” actually reorganizes the data into bins. To avoid confusion we call this data reorganization operation “binning” in this chapter. This algorithm is also an interesting example of where a serial ...