↩ back to Non-Comparison Sorts
A twelfth non-comparison sort, and the first one here that never allocates a bucket array at
all. MSD string sort handles variable-length string
keys by counting each range into R+1 fixed buckets (26 letters plus a sentinel) at
every recursion level, then copying into a fresh auxiliary array — work that scales with
R, the alphabet size, whether or not most of those buckets ever get used. Three-way
radix quicksort (also called multikey quicksort, Bentley & Sedgewick, 1997)
answers the same question — sort strings that don't all share one fixed width — a different way:
instead of bucketing by exact character value, it three-way partitions a range on a single
character position, the same low/equal/high split a ternary search tree encodes as a persistent
3-pointer node, applied here as a one-shot in-place scan instead. Only the low and high partitions
ever get compared again at the same character position, the way quicksort recurses on both sides of a partition; the equal
partition — every string sharing the pivot's character here — moves one position deeper, the way
MSD string sort's own buckets do. No R ever appears in the code below: this is the one
entry in this category whose cost per level doesn't depend on how large the alphabet is, only on
how many strings are actually in range — see Complexity for what that's worth in practice.
It's also the one entry here that isn't quite "non-comparison" in the narrowest sense: it does
use </=/> on character codes, an operator every other
sort in this category avoids entirely in favor of direct indexing. What still separates it from a
comparison sort is what gets compared: one
character of two keys at a time, not one whole key against another. The Ω(n log
n) floor a comparison sort can't escape is a bound on distinguishing n arbitrary
keys using whole-key comparisons alone; a sort that looks inside a key one character at a time isn't
playing that game, the same escape hatch counting sort and radix sort use by indexing instead of
comparing — this entry just uses a three-way comparison as its indexing operator instead of an
array lookup.
Enter a comma-separated list of lowercase words (letters a–z
only, this demo caps it at 10 words of 14 characters or fewer). Step through: at each range and
character position, the leftmost word in that range becomes the pivot (bordered
cell). Every other word in the range is scanned once (accent-filled cell) and compared against the
pivot's character at the current position — less swaps toward the front of the
range, greater swaps toward the back, equal just advances. What's
left is three groups, marked with a boundary line at the start of the equal group and the start of
the high group: low, equal, and high. Low and high recurse at the same character position
(shaded range); equal recurses one position deeper, unless the pivot itself had already run out of
characters, in which case that group is done — see Why it works.
One recursive function, sort(a, lo, hi, d): sort the range a[lo..hi]
by character position d. A range of zero or one words is already sorted. Otherwise,
one pass three-way partitions the range around v, the pivot's character at position
d (a[lo] itself, exactly like plain quicksort's own choice of a fixed
pivot position — see Pitfalls for what that choice costs). A scan pointer i walks from
lo+1; a low pointer lt and high pointer gt start at
lo and hi. At each step, compare a[i]'s character at
d against v: if it's less, swap it down to lt and advance
both lt and i; if it's greater, swap it up to gt and only
retreat gt (the newly-swapped-in word at i hasn't been checked yet, so
i itself doesn't move); if it's equal, just advance i. When i
passes gt, the range is exactly three groups: a[lo..lt-1] all less than
v at position d, a[lt..gt] all equal to v, and
a[gt+1..hi] all greater.
The low and high groups still need sorting among themselves — being less than the
pivot's character only orders them against the pivot, not against each other, since two words can
both be less than v while differing from one another at this exact position ('a'
and 'b' are both less than 'm', but still need their own comparison). That's
why they recurse at the same d, not d+1 — skipping straight to the
next character throws away a comparison these words still owe each other (see Pitfalls for what that
costs, measured). The equal group is different: every word in it shares the identical character
v at position d by construction, so there's nothing left to learn from
that position — it recurses at d+1, exactly the way MSD string sort's own buckets move one
character deeper. One exception: if v is the sentinel value (the pivot had already run
out of characters at position d), every word sharing it has also already ended at
exactly this length — they're identical strings with nothing left to compare, and recursing would
just call charAt past the end of an exhausted string forever. The reference
implementation below guards this explicitly with if (v >= 0), the exact same role MSD string sort's sentinel-bucket exclusion
plays, enforced by a comparison here instead of a separate bucket.
Termination follows the same two-part argument MSD string sort's own recursion does, just
phrased over a partition instead of a bucket split: the low and high recursive calls always operate
on a strictly smaller range than their parent (the pivot itself is excluded from both, and lands in
the equal group), so repeated low/high recursion at a fixed d can't continue forever.
The equal call doesn't have to shrink the range at all — every word could share the pivot's
character — but it always increases d, and d is capped by the longest word
still being distinguished; the moment every remaining word in a group has been reduced to the
sentinel, the guard above stops it cold.
This is the exact scheme the demo above steps through, verified against
Array.prototype.sort across 30,000 random trials, a further 20,000 trials that force at
least one prefix relationship per trial, and 10,000 trials drawn from a small pool engineered for
heavy duplication — zero mismatches in all three, plus a 50-identical-string stress case to confirm
the sentinel guard actually prevents runaway recursion:
// -1 is the sentinel: "this word has already ended by position d"
function charAt(word, d) {
return d < word.length ? word.charCodeAt(d) - 97 : -1;
}
function threeWayRadixQuicksort(words) {
const a = words.slice();
sort(a, 0, a.length - 1, 0);
return a;
function sort(a, lo, hi, d) {
if (hi <= lo) return; // 0 or 1 words — already sorted
let lt = lo, gt = hi;
const v = charAt(a[lo], d); // pivot: the leftmost word's character at d
let i = lo + 1;
while (i <= gt) {
const t = charAt(a[i], d);
if (t < v) swap(a, lt++, i++);
else if (t > v) swap(a, i, gt--); // i stays — the swapped-in word is still unchecked
else i++;
}
sort(a, lo, lt - 1, d); // low group: same d, still needs its own ordering
if (v >= 0) sort(a, lt, gt, d + 1); // equal group: one character deeper (skip if pivot ended)
sort(a, gt + 1, hi, d); // high group: same d
}
function swap(a, i, j) { const t = a[i]; a[i] = a[j]; a[j] = t; }
}Notice what's absent compared to MSD string sort's own reference
implementation: no R, no count array, no auxiliary array. Every move here is a
single swap inside the original array — the partition is entirely in place, the same
property quicksort has and MSD string sort's fresh-array
copy per level doesn't.
Recursing the low and high groups one character deeper instead of at the same position
is a genuine wrong order, not just slower. It looks tempting to treat every recursive call
the same way and always advance d, symmetric with the equal group. But the low and high
groups are only known to be less-than or greater-than the pivot's character — two words that both
land in the low group can still differ from each other at that very position, and skipping
it discards a comparison they still need. Checked directly: across 30,000 random trials, this
variant produced a wrong order in 22,831 of them (76.1%). A clean minimal
counterexample: ["cx","ba","aa"] — pivot "cx" puts both "ba"
and "aa" in the low group (both start below 'c'), but jumping to position 1
compares their second characters ('a' vs. 'a', a tie) instead of
their first ('b' vs. 'a'), producing ["ba","aa","cx"] where
the correct order is ["aa","ba","cx"].
Dropping the v >= 0 guard hangs on duplicate keys — it doesn't
misorder them. Once a pivot's character at position d is the sentinel, every
word sharing it has also already ended at exactly this length, so they're identical strings with no
characters left. Recursing into that group anyway doesn't crash outright the way MSD string sort's
equivalent bug does (its bucket read would go out of bounds); here charAt just keeps
returning -1 for an exhausted string forever, so the pivot stays the sentinel and the
whole group re-partitions against itself at every depth, without end. Checked directly: across
20,000 trials engineered to force at least one duplicate or prefix relationship, this variant hung
in 8,886 of them (44.4%); even across 20,000 pure random trials with no
forced relationship, it still hung in 169 (0.84%) — any two identical words
anywhere in the input are enough. A clean minimal pair shows the exact boundary: ["sea",
"sea"] hangs, but ["sea", "seashells"] — a prefix relationship, not a duplicate —
doesn't, because those two are never simultaneously exhausted at the same position; they part ways
at position 3 (sentinel vs. 's') before the bug can ever trigger.
Time: expected O(n log n) character comparisons on random keys,
worst case O(n·w) where w is the longest word's length — the same
order MSD string sort's own worst case has, for the same reason (a range where every word shares a
long common prefix forces recursion through every one of those shared characters before anything
separates). Measured directly: on random word sets from n=50 up to n=1,600,
character comparisons per n log₂n stayed roughly flat between 0.81 and 0.93 — the
signature of O(n log n) growth, not a rising ratio. A second, independent measurement
found the worst case is reachable more easily than MSD string sort's own "long shared prefix" trigger:
because the pivot is always the range's leftmost word (a fixed position, exactly plain quicksort's own documented weakness), an
already-sorted input degrades every partition to a range of size 1 and a range of size
n-1, the same failure quicksort's own Pitfalls section names. A staircase construction
("a", "ab", "abb", ..., already sorted, word length growing
with n) measured comparisons converging to almost exactly 0.5·n·w
from n=50 to n=1,600 — genuine Θ(n·w), not an
artifact of small n. This site's reference implementation keeps the fixed-pivot rule
deliberately, the same choice quicksort's own reference
implementation makes, for the same reason: it's the simplest version to verify by hand, and a
random or median-of-three pivot (quicksort's own real-world fix) removes the reliable trigger without
removing the theoretical worst case.
What's genuinely different from every other Non-Comparison Sort entry here: per-level
cost has no term that depends on R, the alphabet size — MSD string sort and American flag sort both size a count array to
R+1 or more at every recursion level, whether or not most of those buckets ever hold
anything. Measured directly on the same 200 six-character words (only 5 distinct letters actually
used) at growing alphabet sizes: three-way radix quicksort's operation count stayed at exactly 1,496
regardless of R, while a simulated MSD-style count-array cost climbed from 3,080 ops at
R=26 (2.1× three-way's cost) to 7,209,180 at R=65,536 (4,819×)
to 122,552,540 at R=1,114,112, the full Unicode code point range (81,920×). Sorting
Unicode strings — or any keyspace too large or too sparse to size a bucket array to — is exactly where
this entry wins over its bucket-based siblings.
Space: O(w) for the recursion stack, no auxiliary array at any
depth — every move is an in-place swap. That matches American flag sort's own in-place
permutation (also no fresh array per level) but goes one step further: American flag sort's swap
chains still need an O(R) count array per active level to compute bucket boundaries
before it can start swapping, while this entry's partition needs nothing sized by R at
all.
Not stable: the swaps that move a word into the low or high group can reorder it past an equal-keyed word it started behind. Measured directly: sorting duplicate-heavy inputs drawn from a small pool of repeated keys produced at least one pair of equal keys in the wrong original order in 83.8% of 2,000 trials — the same trade American flag sort and Flash Sort make for their own in-place permutations.
See Choosing a Non-Comparison Sort for how this compares against the site's other eleven Non-Comparison Sorts entries — short version: reach for this over MSD string sort specifically when the alphabet is large, sparse, or unknown in advance (Unicode text, arbitrary comparable objects per position), since it's the only entry here whose cost never depends on how big that alphabet actually is.