Samplesort

Samplesort is a sorting algorithm that is a divide and conquer algorithm often used in parallel processing systems. 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 from the -element sequence, and determining the range of the buckets by sorting the sample and choosing elements from the result. These elements (called splitters) then divide the array into approximately equal-sized buckets. Samplesort is described in the 1970 paper, "Samplesort: A Sampling Approach to Minimal Storage Tree Sorting", by W. D. Frazer and A. C. McKellar.

Samplesort is a sorting algorithm that is a divide and conquer algorithm often used in parallel processing systems. 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 from the -element sequence, and determining the range of the buckets by sorting the sample and choosing elements from the result. These elements (called splitters) then divide the array into approximately equal-sized buckets. Samplesort is described in the 1970 paper, "Samplesort: A Sampling Approach to Minimal Storage Tree Sorting", by W. D. Frazer and A. C. McKellar. select S = [S 1 , ..., S (p−1)k ] randomly from // select samples sort // sort sample [s 0 , s 1 , ..., s p−1 , s p ] k , S 2k , ..., S (p−1)k , ∞] // select splitters /* Step 2 */ for each a in A find such that s j−1 j place in bucket b j /* Step 3 and concatenation */ return concatenate(sampleSort(b 1 ), ..., sampleSort(b k )) The pseudo code is different from the original Frazer and McKellar algorithm. In the pseudo code, samplesort is called recursively. Frazer and McKellar called samplesort just once and used quicksort in all following iterations. O\left(c\left(\frac{n}{p}\right) \right) where c(n) is the complexity of the underlying sequential sorting method. Often c(n) = n \log(n) . The number of comparisons, performed by this algorithm, approaches the information theoretical optimum \log_2(n!) for big input sequences. In experiments, conducted by Frazer and McKellar, the algorithm needed 15% fewer comparisons than quicksort. X_i := \begin{cases} 1, & \text{if } s_i \in \left\langle e_j, \dots, e_j + (1 + \epsilon) \cdot \dfrac{n}{p}\right\rangle\\ 0, & \text{otherwise} \end{cases}, X := \sum_{i=0}^{S \cdot p - 1}X_i For the expected value of X_i holds: E(X_i) = P(X_i = 1) = \dfrac{1 + \epsilon}{p} This will be used to estimate P_\text{fail} : P(X Using the Chernoff bound now, it can be shown: P_\text{fail} = n \cdot P(X j := 1 repeat log 2 (p) times j := 2j + (a > t j ) j := j − p + 1 Since the number of buckets is known at compile time, this loop can be unrolled by the compiler. The comparison operation is implemented with predicated instructions. Thus, there occur no branch mispredictions, which would slow down the comparison operation significantly. ==References== Frazer and McKellar's original paper DOI.org DOI.org Adapted for use on parallel computers: http://citeseer.ist.psu.edu/91922.html http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.49.214

Text derived from https://en.wikipedia.org/w/index.php?oldid=1374888028 under CC BY-SA 4.0; modifications have been made.