# 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.

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++).