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 ...)
Aggregate parent (I am a part of or used in ...)
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.
Explained in a message about J sort posted in 1997.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 24 November 2008.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "shuffle sort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 24 November 2008. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/shuffleSort.html