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

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 11 February 2019.

HTML page formatted Wed Mar 13 12:42:46 2019.

Cite this as:

Paul E. Black, "pigeonhole sort", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 11 February 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/pigeonholeSort.html