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

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)

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