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 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. Samplesort is described in the 1970 paper, "Samplesort: A Sampling Approach to Minimal Storage Tree Sorting", by W. D. Frazer and A. C. McKellar.
Algorithm Samplesort is a generalization of quicksort. Where quicksort partitions its input into two parts at each step, based on a single value called the pivot, samplesort instead takes a larger sample from its input and divides its data into buckets accordingly. Like quicksort, it then recursively sorts the buckets. To devise a samplesort implementation, one needs to decide on the number of buckets p. When this is done, the actual algorithm operates in three phases:
Sample p−1 elements from the input (the splitters). Sort these; each pair of adjacent splitters then defines a bucket. Loop over the data, placing each element in the appropriate bucket. (This may mean: send it to a processor, in a multiprocessor system.) Sort each of the buckets. The full sorted output is the concatenation of the buckets. A common strategy is to set p equal to the number of processors available. The data is then distributed among the processors, which perform the sorting of buckets using some other, sequential, sorting algorithm.
Pseudocode The following listing shows the above-mentioned three step algorithm as pseudocode and shows how the algorithm works in principle. In the following, A is the unsorted data, k is the oversampling factor, discussed later, and p is the number of splitters.
function sampleSort(A[1..n], k, p) // if average bucket size is below a threshold switch to e.g. quicksort if n / k < threshold then smallSort(A) /* Step 1 */ select S = [S1, ..., S(p−1)k] randomly from // select samples sort S // sort sample [s0, s1, ..., sp−1, sp] <- [-∞, Sk, S2k, ..., S(p−1)k, ∞] // select splitters /* Step 2 */ for each a in A find j such that sj−1 < a <= sj place a in bucket bj /* Step 3 and concatenation */ return concatenate(sampleSort(b1), ..., sampleSort(bk))
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.
Complexity The complexity, given in Big O notation, for a parallelized implementation with p {\displaystyle p} processors: Find the splitters.
O ( n p + log ( p ) ) {\displaystyle O\left({\frac {n}{p}}+\log(p)\right)}
Send to buckets.
O ( p ) {\displaystyle O(p)} for reading all nodes
O ( log ( p ) ) {\displaystyle O(\log(p))} for broadcasting
O ( n p log ( p ) ) {\displaystyle O\left({\frac {n}{p}}\log(p)\right)} for binary search for all keys
O ( n p ) {\displaystyle O\left({\frac {n}{p}}\right)} to send keys to bucket Sort buckets.
O ( c ( n p ) ) {\displaystyle O\left(c\left({\frac {n}{p}}\right)\right)} where c ( n ) {\displaystyle c(n)} is the complexity of the underlying sequential sorting method. Often c ( n ) = n log ( n ) {\displaystyle c(n)=n\log(n)} . The number of comparisons, performed by this algorithm, approaches the information theoretical optimum log 2 ( n ! ) {\displaystyle \log _{2}(n!)} for big input sequences. In experiments, conducted by Frazer and McKellar, the algorithm needed 15% fewer comparisons than quicksort.
Sampling the data The data may be sampled through different methods. Some methods include:
Pick evenly spaced samples. Pick randomly selected samples.
… excerpt ends here. Continue reading the full article.
