This site's companion guide, Choosing a
Comparison Sort, picks between seven sorts that all work the same way: compare pairs of
elements, and live under the Ω(n log n) floor that comparing implies. The ten
Non-Comparison Sorts on this site —
Counting Sort,
Pigeonhole Sort,
Bucket Sort,
Radix Sort,
American Flag Sort,
Bead Sort,
Flash Sort,
Spreadsort,
Proxmap Sort, and
MSD String Sort — dodge that floor by extracting
structure from the keys themselves instead of comparing them, and in exchange every one of them
needs the keys to have a specific shape before it works at all. Picking between them isn't "which
is fastest" so much as "which of these ten shapes does your data actually have" — that question,
not raw speed, is what this guide sorts by.
In order, cheapest to check first: Are the keys strings that don't all share one fixed
width? Only one of the ten handles that case, and nothing else below applies if so — every
other entry here silently assumes a key has a well-defined value (or digit, or character) at every
position it looks at. Otherwise, are the keys real numbers spread continuously over
a range, rather than integers? Four of the remaining nine handle that case. If the
keys are integers, is the range k close to the element count n? A
small range settles it outright. If the range is too wide for that, does the sort need to
stay stable — or preserve payload records tied to each key — or is memory tighter than time?
This is the last question because it only matters once the first three have already ruled out the
cheaper options.
MSD string sort answers a question none of the
other nine even ask: what if the keys don't all have the same number of positions to look at?
Every other entry in this guide — radix sort's digits, American flag sort's digits, bucket/Flash
Sort/Spreadsort/Proxmap's arithmetic buckets, counting/pigeonhole sort's direct values — assumes a
key has a well-defined value at whatever position the sort is currently examining. A string doesn't:
"sea" runs out of characters at position 3 while "seashells" still has six
to go. MSD string sort handles that by reserving one extra sentinel bucket per recursion level for
keys that have already ended, deliberately excluded from further recursion since two keys that both
end at the same position are, by construction, identical strings. Its own complexity section measured the
payoff of that design directly: recursion depth adapts to how quickly keys actually diverge, from
61.3% of a naive full-length character scan on random words down to a genuine O(n·w)
worst case only when keys share a long common prefix. If the keys are fixed-width — every one is
exactly the same number of digits or bytes — reach for radix sort or American flag sort below
instead; this is the one entry built specifically for when that assumption doesn't hold.
Five of these nine entries need integer keys, one way or another. Bucket sort, Flash Sort, Spreadsort, and Proxmap sort are the exceptions: all four classify values by
an arithmetic formula over a known range rather than an exact digit, and all four need that range
to spread its values roughly uniformly to hit their best case. Bucket sort and
Flash Sort split the exact same way radix sort and American flag sort
make below over integer keys: bucket sort distributes values into k fresh per-bucket
arrays, sorts each with a plain comparison sort, and concatenates — expected O(n+k)
space and time. Flash Sort permutes in place instead, the identical swap-chain-with-cursors
technique American flag sort uses for its own digit buckets, and finishes with one flat
insertion-sort pass over the whole array rather than per-bucket, since its classes (unlike a digit)
only guarantee relative order between classes, not exact equality within one — O(m)
space for the class bookkeeping, independent of n.
The uniformity assumption is load-bearing for both, not decorative: bucket sort's own pitfalls measured 200 uniformly
random values over [0, 1) at 90 total insertion-sort comparisons across every bucket,
versus the same 200 values drawn from the narrow range [0.50, 0.51) collapsing into
just 2 of the 200 buckets for 5,235 comparisons — roughly 58× more work sorting the exact
same count of values. Flash Sort's own complexity
section found the identical failure mode from the identical cause: 95% of a 500-element array
packed into one narrow sub-range costs 73.8× the comparisons of uniformly spread data at the
same size, both algorithms degrading silently to plain insertion sort on whichever class or bucket
absorbed everything — nothing crashes, the output is still correctly sorted, but the whole point of
classifying first is lost. Bucket sort is also a hybrid in a second sense: the per-bucket sort is a
real comparison sort, so a skewed-enough input can still cost Ω(n log n) on top
of the arithmetic distribution step, where Flash Sort's single flat finishing pass stays a plain
O(n²) insertion sort in the same skewed case.
Spreadsort is what happens when that shared
uniformity assumption is treated as fixable rather than fatal: instead of finishing an oversized
bucket in place (Flash Sort) or with a per-bucket comparison sort (bucket sort), it rescans just
that bucket's own min/max and reclassifies it as a brand-new sub-problem, recursing until a region
is small enough to finish cheaply. Its own
complexity section measured that recursion directly against the identical clustered-input
construction the other two collapse on: up to 10,290× fewer comparisons than a single-level
classifier at n=2,000, a gap that widens with n rather than staying
fixed. The trade is recursion overhead and stack space instead of Flash Sort's single flat pass —
worth it exactly when the input might be clustered rather than genuinely uniform, since a uniform
input pays that overhead for no benefit over Flash Sort's simpler single pass. Recursion doesn't
make the uniformity assumption disappear entirely, either: a range engineered so one value dominates the local
max at every level still collapses toward O(n²), the same worst case its two
siblings never escape.
Proxmap sort takes the same arithmetic mapping in a
different direction: instead of a separate list per bucket (bucket sort), it counts hits per bucket
first and prefix-sums those counts into fixed start offsets — counting sort's own trick, run over arithmetic buckets
instead of exact integer keys — so every bucket's window in one shared output array is claimed
before a single value is placed. What's left is a small insertion confined to that window, never a
separately allocated list. Its own complexity
section is explicit that this doesn't change the time bound or the uniformity weakness at all —
the identical narrow-range construction above costs it roughly 57× more comparisons at
n=200, the same order of magnitude as its three siblings' own numbers — only the memory
layout: three small O(k) integer arrays and one O(n) output array, instead
of k separately allocated per-bucket lists holding the same elements. Reach for it over
bucket sort specifically when that per-bucket allocation overhead isn't worth paying.
Once the keys are integers, the next question is whether the range k stays close
to n. If it does, counting sort is
O(n+k) and immune to input order entirely — no adversarial arrangement makes it
slower, unlike quicksort's pivot-dependent worst case. It counts occurrences per value, prefix-sums
those counts into placement offsets, then places each element directly — O(n+k)
space for a k+1-slot integer array plus the output.
Pigeonhole sort reaches the exact same
O(n+k) time bound a more literal way — give every possible value its own hole, drop
each element into its hole, then walk the holes in order and drain them — and needs the same
precondition (small k relative to n) to be worth using at all. But its own pitfalls are explicit that this isn't
a different failure mode from counting sort's, "just more expensive to hit": counting sort's
k+1 slots are bare integers, pigeonhole sort's are lists that have to exist whether or
not anything ever lands in them, so sorting 12 values spread across a range of 10,000 allocates
10,001 mostly-empty lists instead of 10,001 zeroed integers — strictly more overhead for
the identical result. There's no input where pigeonhole sort is the better choice over counting
sort; its page exists to make that contrast concrete, the same role bubble sort plays opposite
insertion sort in the comparison-sort guide, not because it's a live candidate.
When k is too large for counting sort to allocate directly — a million 32-bit
integers spanning the full int range, say — but the keys still have a fixed digit
width, radix sort and American flag sort both process one digit at a
time instead of the whole key at once, at the same O(d·(n+k)) time bound
(d digit passes, each an O(n+k) counting sort with a fixed
k — 10 for a decimal digit, 256 for a byte). They differ in direction and in what
that direction costs.
Radix sort works least-significant-digit first, leaning on every pass being stable so the
ones-digit order survives underneath the tens-digit pass, and so on. Its own pitfalls found that a single unstable
pass — not just a rare edge case, roughly 70% of randomized trials — produces a final array that
isn't sorted at all, not merely tie-order-wrong the way an unstable counting sort pass is. The
cost of that guarantee is a fresh O(n+k) output array allocated and discarded on
every one of the d passes.
American flag sort takes the opposite route: most-significant-digit first, recursing into each
digit's own bucket, and instead of a fresh output array it counts, computes bucket boundaries, and
permutes values into place inside the input array via swap chains. That trades away
stability entirely — nothing preserves tie order across a swap-based permutation — for
O(k) space per active recursion level instead of O(n+k) per pass, an
O(k·d) total that's a constant for fixed-width keys, genuinely smaller than
radix sort's per-pass buffer. Its own
pitfalls note the in-place permutation is easy to get subtly wrong in a way radix sort's
fresh-array approach never risks — a naive fixed loop over each bucket's index range disagreed
with a correct sort on roughly 41% of 5,000 seeded trials, because a swapped-in value can land at
an index the loop already passed and never get rechecked. So: reach for radix sort when the sort
needs to stay stable or memory isn't the bottleneck; reach for American flag sort when memory is
tighter than time and nothing depends on tie order surviving.
Bead sort answers a different question than the other
eight. It's a natural algorithm (Arulanandham, Calude & Dinneen, 2002) — built as
actual beads on actual rods under actual gravity, where every column of an abacus-like grid
settles simultaneously, in parallel, in whatever time physical beads take to fall. That's a
genuinely different machine model, not a software one; the O(n·max) this
site's simulation measures (a sequential pass per column) is what a JavaScript loop does standing
in for gravity, not a claim about what physical hardware could do. In software, that
O(n·max) bound loses to counting sort for essentially any range wider than
tiny: its own pitfalls note grid width tracks the
largest raw value, not the value spread, so [1000, 1001, 1002] costs
O(n·1002) here against counting sort's offset-adjusted O(n+3). It
also can't carry a payload — the settled grid records how many beads landed in each column, never
which original row contributed which bead, so given (key, payload) records it can
sort the keys but loses track of which payload belongs with which one. Reach for it only when the
question is the natural-algorithm model itself (teaching, or literal analog hardware), not when
sorting non-negative integers in software — counting sort dominates it on every axis that matters
there.
| Entry | Time | Space | Stable? | Reach for it when |
|---|---|---|---|---|
| Bucket Sort | O(n+k) expected, O(n²) worst | O(n+k) | yes (with a stable per-bucket sort) | real-valued keys, roughly uniform over a known range |
| Counting Sort | O(n+k) | O(n+k) | yes | integer keys, range k close to n |
| Pigeonhole Sort | O(n+k) | O(n+k), larger constant than counting sort | yes | teaching the contrast with counting sort — not a live candidate |
| Radix Sort | O(d·(n+k)) | O(n+k) per pass | yes | wide fixed-width integer keys, stability required |
| American Flag Sort | O(d·(n+k)) | O(k·d), in-place | no | wide fixed-width integer keys, memory tighter than time |
| Bead Sort | O(n·max) simulated | O(n·max) | no (no payload at all) | the natural-algorithm model itself, not production software |
| Flash Sort | O(n) average, O(n²) worst | O(m), in-place | no | continuous or wide-range numeric keys, memory tighter than time |
| Spreadsort | O(n) average, O(n²) adversarial worst | O(m) per region, O(log n)–O(n) recursion depth | no | continuous numeric keys that might be clustered, not just wide-range |
| Proxmap Sort | O(n+k) average, O(n²) worst | O(n+k), smaller constant than Bucket Sort | yes | continuous or wide-range numeric keys, per-bucket list overhead isn't worth paying |
| MSD String Sort | O(n logᵣR n) expected, O(n·w) worst | O(n + R·w) | yes | string keys that don't all share one fixed width |