(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
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 19 June 2006.
HTML page formatted Mon Feb 2 13:10:40 2015.
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: http://www.nist.gov/dads/HTML/rapidSort.html