NIST

shuffle sort

(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

More information

Explained in a message about J sort posted in 1997.


Go to the Dictionary of Algorithms and Data Structures home page.

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