(algorithm)
Definition: A distribution sort algorithm that begins by removing the first 1/8 of the n items, sorting them (recursively), and putting them in an array. This creates n/8 buckets to which the remaining 7/8 of the items are distributed. Each bucket is then sorted, and the buckets are concatenated.
Generalization (I am a kind of ...)
distribution sort.
Aggregate parent (I am a part of or used in ...)
J sort.
See also American flag sort, distributive partitioning sort, B-tree.
Note: Shuffle sort can be thought of as forming very wide trees, like B-tree with m=n/8, to sort efficiently in many cases.
Shuffle sort estimates the distribution of the items to be sorted by examining the first n/8 items. Distributive partitioning sort estimates the distribution by approximating the median and linearly interpolating from the minimum to the median and from the median to the maximum.
Author: PEB
Explained in a message about J sort posted in 1997.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 24 November 2008.
HTML page formatted Mon Feb 2 13:10:40 2015.
Cite this as:
Paul E. Black, "shuffle sort", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 24 November 2008. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/shuffleSort.html