↩ back to Non-Comparison Sorts
Counting sort gets to O(n+k) by
never storing the elements themselves in its buckets at all — just an integer count per value,
turned into a running total, then used to compute exactly where each element belongs. Pigeonhole
sort reaches the same bound a more literal way: give every possible key value its own hole, drop
each element straight into the hole matching its value, then walk the holes in order and empty
them out. No running total, no computed index — the elements themselves sit in the holes, and
since the holes are visited in increasing key order, reading them off in order is the
sorted array. It's the most direct arithmetic-free non-comparison sort on the site: given
k holes and a way to drop something into hole number v, sorting falls
out for free.
Enter a comma-separated list of integers (this demo caps it at 12 elements with a spread of 15
between smallest and largest, tighter than counting
sort's demo — see Why it works for why pigeonhole sort specifically wants the value range
close to the element count). Step through two phases: distributing each input
element into the hole matching its exact value, then collecting the holes in
order, 0 through k, draining each one into the output. When the loaded array has a
repeated value, every bar and hole entry carries a small subscript showing its original input
index, so you can watch exactly which copy ends up where. The checkbox controls which end of each
hole gets drained first.
Two passes, each doing the most direct thing possible. First, distribute: walk
the input once, and for each element v, append it to holes[v - min] —
a plain list, not a counter. Second, collect: walk the holes 0
through k in order and drain each one into the output. Every element in
holes[b] is, by construction, equal to every other element in that same hole — there
is nothing left to sort within a hole, only an arrival order to preserve. Appending during
distribution and draining front-first during collection means the first copy of a value seen in
the input is also the first one written to the output, which is exactly what
stability requires; see Pitfalls for what happens if
either end of that pipeline runs backwards.
The reason this demo keeps the value range close to the element count — where
counting sort's own demo happily allows k
up to twice n — is that pigeonhole sort was described for exactly that regime: roughly
one hole per element, most holes non-empty. Counting sort's count-then-prefix-sum-then-place
scheme is a genuine improvement on the same idea for the general case, because a hole that turns
out to be empty costs it nothing but a single zero in an integer array, while an empty hole here
still has to exist as an allocated list. When k is much larger than n,
that difference compounds fast — see Pitfalls.
Supports negative values via an offset (min), the same scheme
counting sort uses. This is the exact scheme the demo
above steps through, with the checkbox controlling shift() versus pop()
in the collect loop:
function pigeonholeSort(arr) {
if (arr.length === 0) return [];
const min = Math.min(...arr);
const max = Math.max(...arr);
const holes = Array.from({ length: max - min + 1 }, () => []);
for (const v of arr) holes[v - min].push(v); // distribute
const output = [];
for (const hole of holes) { // collect
while (hole.length) output.push(hole.shift()); // front-first: stable
}
return output;
}It still needs small integer keys — and pays more for the privilege than counting sort
does. Both algorithms allocate k+1 slots up front, so both are only sensible
when k stays close to n. But counting sort's slots are bare integers;
pigeonhole sort's are lists that have to exist whether or not anything ever lands in them. Sorting
12 values spread across a range of 15 (this demo's own limit) allocates 16 mostly-full holes —
reasonable. The same 12 values spread across a range of 10,000 would allocate 10,001 holes, all
but 12 of them permanently empty, for no benefit over counting sort's 10,001 zeroed integers except
much higher constant overhead per hole. This isn't a different failure mode from counting sort's
own range pitfall — it's the same one, just more expensive to hit.
Stability depends on both ends of the pipe agreeing on a direction. Load the
default array above, 3, 1, 3, 2, 1, with the checkbox on: the two 1s
(input indices 1 and 4) come out in that same order, and so do the two 3s (indices 0
and 2) — every subscript in the output reads left-to-right in the same relative order it had going
in. Uncheck the box and reload: distribution is unchanged, but collection now drains each hole
back-first (pop() instead of shift()), and both duplicate pairs come out
reversed — 1 at index 4 now precedes the one at index 1. Nothing about the sortedness
of the output changes either way; only the relative order of equal elements does, silently, the
same class of bug counting sort's own
placement-direction pitfall and
selection sort's in-place swap both raise —
a sort that looks perfectly correct on plain numbers can still be unstable underneath.
Time: O(n+k) — one pass to distribute (O(n)), one
pass over every hole to collect (O(n+k): n elements moved plus
k holes visited, even the empty ones). Same bound as
counting sort, for the same reason: no comparisons,
just direct indexing by value. Space: O(n+k) in the same shape as
counting sort's, but with a materially larger constant — k+1 list allocations instead
of k+1 integers, plus every input element copied into a hole on top of the output
array, rather than counted once and placed directly. When k is close to n
the two algorithms cost about the same in practice; when it isn't, that constant is exactly what
the first Pitfall above measures.
See Choosing a Non-Comparison Sort for how this compares against the site's other nine Non-Comparison Sorts entries — short version: there's no input where this beats counting sort outright.