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 twelve
Non-Comparison Sorts on this site —
Counting Sort,
Pigeonhole Sort,
Bucket Sort,
Radix Sort,
American Flag Sort,
Bead Sort,
Flash Sort,
Spreadsort,
Proxmap Sort,
MSD String Sort,
LSD String Sort, and
Three-Way Radix Quicksort — dodge that
floor by never comparing two whole keys against each other, most by extracting structure from the
keys themselves (a digit, a bucket index, a count) instead of comparing at all — three-way radix
quicksort is the one entry that still compares, just one character at a time instead of one whole
key at a time, a finer grain the Ω(n log n) bound doesn't reach. Every one of the
twelve 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 twelve 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? Three of the twelve
handle string keys specifically, split by two further questions — do all the strings
already share one fixed length? If so, LSD string sort's plain per-position passes work
directly. If not, how large or well-bounded is the alphabet? A small, known
alphabet (lowercase letters, bytes) favors MSD string sort's sentinel-bucket recursion; a large,
sparse, or unbounded one (Unicode, or keys that aren't characters at all) favors three-way radix
quicksort's partition, since it never sizes an array to the alphabet in the first place (LSD string
sort has no fallback for the variable-length case at all — see its own Pitfalls). 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 four have already ruled out the cheaper options.
Three of the twelve entries handle string keys. LSD and MSD string sort answer the same fixed-width-or-not question radix sort and American flag sort answer for numbers below — except for numbers that question barely matters (any integer can be thought of as zero-padded to a common width for free), while for strings it's a real fork in the road. LSD string sort takes the fixed-width side: if every key is genuinely, exactly the same length, it runs radix sort's exact count → prefix-sum → place scheme once per character position, 26 buckets instead of 10 digits, starting from the rightmost character. Its own pitfalls are explicit that this isn't a soft preference — feed it strings of different lengths and it doesn't sort them wrong, it crashes outright (100% of 19,507 random trials where lengths actually differed, via an out-of-bounds character read one pass after a too-short word silently drops out of the array entirely).
MSD string sort answers the case LSD string sort
can't: 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, LSD string sort's own characters,
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 have to: "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 — a real cost LSD
string sort never pays (or benefits from): its own complexity section notes it always runs
every one of its W passes over the whole array, whether the keys separate on their
first character or their last. Reach for LSD string sort when the fixed-width guarantee already
holds and its simpler, non-recursive shape is worth it; reach for MSD string sort the moment that
guarantee doesn't hold, at least while the alphabet stays small and known in advance.
Three-way radix quicksort answers the
same variable-width question MSD string sort does, but without ever sizing an array to the alphabet.
MSD string sort counts every range into R+1 fixed buckets at every recursion level,
work that scales with R whether or not most buckets ever hold anything; three-way radix
quicksort three-way partitions the range instead — less-than/equal/greater-than against one
character — so its cost depends only on how many strings are in range, never on the alphabet size.
Its own complexity section
measured the gap directly: on the same 200 six-character words, MSD string sort's simulated bucket
overhead grows from 2.1× three-way radix quicksort's cost at R=26 (ordinary
lowercase letters) to 4,819× at R=65,536 to 81,920× at
R=1,114,112 (the full Unicode code point range) — while three-way radix quicksort's own
cost never moved. It also partitions fully in place, unlike MSD string sort's fresh auxiliary array
per level. The trade is that it does use character comparisons rather than pure indexing (see its own
introduction for why that still isn't a comparison sort in the site's sense), and its fixed-pivot
reference implementation shares plain quicksort's own O(n·w) worst case on
already-sorted input. Reach for MSD string sort when the alphabet is small and bounded (it's the
simpler, more standard choice); reach for three-way radix quicksort the moment the alphabet is large,
sparse, or not even known in advance.
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 |
| LSD String Sort | O(W·(n+R)) | O(n+R) per pass | yes | string keys that already all share one fixed width |
| Three-Way Radix Quicksort | O(n log n) expected, O(n·w) worst | O(w), in-place | no | string keys that don't share one fixed width, alphabet large or unknown in advance |