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 ...)
Specialization (... is a kind of me.)
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.
See the Wikipedia entry.
If you have suggestions, corrections, or comments, please get in touch with Paul E. Black.
Entry modified 19 June 2006.
HTML page formatted Tue Dec 6 16:16:32 2011.
Cite this as:
Paul E. Black, "pigeonhole sort", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed., U.S. National Institute of Standards and Technology. 19 June 2006. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/pigeonholeSort.html