(algorithm)
Definition: A 2-pass sort algorithm that is efficient when the range of keys is approximately equal to the number of items. The first pass allocates an array of buckets, one bucket for each possible key value, then moves each item to its key's bucket. The second pass goes over the bucket array moving each item to the next place in the destination.
Generalization (I am a kind of ...)
range sort.
Specialization (... is a kind of me.)
rapid sort.
See also counting sort.
Note: The bucket array is called the pigeonhole array.
Pigeonhole sort moves items twice: once to the bucket array and again to the final destination. Counting sort builds an auxiliary array then uses the array to compute each item's final destination and move the item there. Since rapid sort only sorts keys, "moving an item in its key's bucket" is just incrementing a count and "moving each item to the destination" is writing the proper number of keys.
Author: PEB
See the Wikipedia entry.
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, "pigeonhole 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/pigeonholeSort.html