Global InformationSamplesort information
Samplesort is a sorting algorithm that is a divide and conquer algorithm often used in parallel processing systems.[1] Conventional divide and conquer sorting algorithms partitions the array into sub-intervals or buckets. The buckets are then sorted individually and then concatenated together. However, if the array is non-uniformly distributed, the performance of these sorting algorithms can be significantly throttled. Samplesort addresses this issue by selecting a sample of size s from the n-element sequence, and determining the range of the buckets by sorting the sample and choosing p−1 < s elements from the result. These elements (called splitters) then divide the array into p approximately equal-sized buckets.[2] Samplesort is described in the 1970 paper, "Samplesort: A Sampling Approach to Minimal Storage Tree Sorting", by W. D. Frazer and A. C. McKellar.[3]
- ^ "Samplesort using the Standard Template Adaptive Parallel Library" (PDF) (Technical report). Texas A&M University.
- ^ Grama, Ananth; Karypis, George; Kumar, Vipin (2003). "9.5 Bucket and Sample Sort". Introduction to Parallel Computing (2nd ed.). ISBN 0-201-64865-2. Archived from the original on 2016-12-13. Retrieved 2014-10-28.
- ^ Cite error: The named reference
Frazer70was invoked but never defined (see the help page).