Samplesort

Samplesort is a divide and conquer sorting algorithm often used in parallel processing systems. Conventional divide and conquer sorts split the array into buckets that are sorted separately and then concatenated, but a non-uniformly distributed array can badly hurt their performance. Samplesort addresses this by taking a sample of size s from the n-element sequence, sorting the sample and choosing p minus 1 of its elements as splitters, which divide the array into p roughly equal-sized buckets. It generalizes quicksort: where quicksort uses one pivot and two parts, samplesort takes a larger sample and several buckets, then sorts the buckets recursively. The algorithm runs in three phases: sample and sort the splitters, place each element in its bucket, and sort each bucket. The sorted output is the concatenation of the buckets, and a common strategy sets p equal to the number of available processors. It is described in a 1970 paper by W. D. Frazer and A. C. McKellar titled Samplesort: A Sampling Approach to Minimal Storage Tree Sorting.