# pigeonhole sort

(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

## Implementation

(Python).
## More information

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 21 April 2022.

HTML page formatted Thu Apr 21 14:52:02 2022.

Cite this as:

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