NIST

rapid sort

(algorithm)

Definition: A 2-pass sort algorithm that is efficient when the range of keys is approximately equal to the number of items and only keys are sorted. The first pass counts the occurrences of each key in an auxiliary array. The second pass goes over the auxiliary array writing the counted number of keys to the destination.

Generalization (I am a kind of ...)
pigeonhole sort.

See also counting sort.

Note: Rapid sort only sorts keys. In other words, items to be sorted consist solely of the key; there is no additional data in items.

More formally, the algorithm is efficient if the range of key is O(number of items), that is, less than or equal to the number of items, with a possible constant multiplier. If the range is much larger than the number of keys, the second pass is inefficient.

Pigeonhole sort moves items, that is, the key and additional data. Since rapid sort sorts keys, it "moves items" by counting or writing occurrences. Counting sort counts the number of occurrences in an auxiliary array then uses the array to compute each item's final destination. In contrast, rapid sort uses the auxiliary array to write the keys in the final destination.

Author: PEB

Implementation

Patrick Eberhart's description and illustration (Visual Basic and C++).
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 19 June 2006.
HTML page formatted Fri Feb 23 10:06:08 2018.

Cite this as:
Paul E. Black, "rapid sort", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 19 June 2006. (accessed TODAY) Available from: https://www.nist.gov/dads/HTML/rapidSort.html