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

Get Structured Parallel Programming now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.