# Pigeonhole Sort

# Pigeonhole Sort

Pigeonhole sort is a direct address sorting algorithm for integers in a small contiguous range. It creates one slot, or pigeonhole, for each possible key value, places elements into their matching slot, then scans the slots in order to rebuild the sorted array.

It is close to counting sort, but the usual presentation stores the actual elements in holes rather than only their counts.

## Problem

Given an array $A$ of $n$ integers where every value lies in a known range $[\min, \max]$, sort the array.

The range size is:

$$
r = \max - \min + 1
$$

## Idea

Allocate $r$ holes. Value $x$ maps to hole:

$$
x - \min
$$

Then place each value into its hole and read the holes from left to right.

## Algorithm

```text id="p4k9xz"
pigeonhole_sort(A):
    lo = minimum(A)
    hi = maximum(A)
    r = hi - lo + 1

    holes = [empty list for _ in range(r)]

    for x in A:
        holes[x - lo].append(x)

    i = 0
    for h from 0 to r - 1:
        for x in holes[h]:
            A[i] = x
            i += 1

    return A
```

## Example

Let:

$$
A = [8, 3, 2, 7, 4, 6, 8]
$$

Here:

$$
\min = 2,\quad \max = 8,\quad r = 7
$$

The holes are:

| hole | value | contents |
| ---- | ----- | -------- |
| 0    | 2     | 2        |
| 1    | 3     | 3        |
| 2    | 4     | 4        |
| 3    | 5     | empty    |
| 4    | 6     | 6        |
| 5    | 7     | 7        |
| 6    | 8     | 8, 8     |

Reading the holes in order gives:

$$
[2, 3, 4, 6, 7, 8, 8]
$$

## Correctness

Each element $x$ is placed into the unique hole whose index is $x - \min$. Therefore each hole contains exactly the elements equal to its associated value.

The final scan visits holes in increasing key order. Since all elements in earlier holes are smaller than all elements in later holes, the rebuilt array is sorted and contains exactly the original elements.

## Complexity

Let:

* $n$ be the number of elements
* $r = \max - \min + 1$ be the range size

Time:

$$
O(n + r)
$$

Space:

$$
O(n + r)
$$

If each hole stores only a count, the space can be reduced to:

$$
O(r)
$$

## Properties

| property              | value                                  |
| --------------------- | -------------------------------------- |
| stable                | yes, if holes preserve insertion order |
| in place              | no                                     |
| comparison based      | no                                     |
| requires integer keys | yes                                    |
| best for              | small contiguous ranges                |

## When to Use

Use pigeonhole sort when the input keys are integers and the range size is close to the number of elements.

It is inefficient when the range is large compared with $n$, because it allocates one hole for every possible value, including values that may not appear.

## Implementation (Python)

```python id="x7m2qa"
def pigeonhole_sort(a):
    if not a:
        return a

    lo = min(a)
    hi = max(a)
    holes = [[] for _ in range(hi - lo + 1)]

    for x in a:
        holes[x - lo].append(x)

    i = 0
    for hole in holes:
        for x in hole:
            a[i] = x
            i += 1

    return a
```