↩ back to Non-Comparison Sorts
A tenth non-comparison sort, and the first on this site whose keys don't all have the same
width. Radix sort and American flag sort both process one digit at a
time, but both quietly assume every key has the same number of digits — there's always a well-defined
"tens place" to look at. Strings don't have that guarantee: "sea" is three characters,
"seashells" is nine, and by the time a most-significant-character pass reaches position 3,
"sea" has nothing left to compare while "seashells" still has six characters
to go. MSD string sort (the "most significant digit" idea American flag sort already uses, generalized
from Sedgewick's own string-sorting chapter) handles that directly: every recursion level gets one
extra bucket — call it bucket ∅ — reserved for keys that have already run out of
characters at this depth, so a shorter key never crashes into an out-of-bounds read and never gets
silently skipped. Like American flag sort it recurses most-significant-character first; unlike American
flag sort it isn't in-place — each recursion level counts hits per bucket, prefix-sums those into
fixed offsets, and writes into a fresh auxiliary array, the same three-pass shape Proxmap sort already uses over numeric buckets, just applied
per character position instead of once.
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, every word in that range is counted into a bucket — its character at the
current position, or ∅ if the word has already ended — those counts become each
bucket's start offset via a prefix sum, then every word is placed
into a fresh array at its bucket's next open slot. Any bucket left holding more than one word then
recurses, narrowed to just that bucket's range, one character position deeper. The
shaded cells mark the active range; the bordered cell is the word currently being counted or placed;
settled cells (down to a range of one word, or fully drained of any further recursion) turn solid.
The whole sort is one recursive function, sort(a, lo, hi, d): sort the range
a[lo..hi] by looking only at each word's character at position d. A range of
zero or one words is already sorted (the base case); otherwise, three passes over exactly that range,
never any other:
Count. Walk a[lo..hi] once. For word w, its bucket is
charAt(w, d) — the character at position d if w is at
least d+1 characters long, or the sentinel value if w has already ended.
Increment that bucket's hit count. Map. Turn hit counts into start offsets with a
prefix sum, the identical move Proxmap sort's own
"why it works" section makes over numeric buckets — except here there are 27 buckets fixed in
advance (26 letters plus the sentinel) instead of one per input value. Place. Walk
a[lo..hi] a second time, writing each word into a fresh auxiliary array at its bucket's
next open offset, then copy the auxiliary array back over a[lo..hi].
That regroups the range by one character position, exactly the way a single American flag sort pass
regroups by one digit. The difference is what happens next. American flag sort recurses into every
multi-element bucket at the next digit, because every key still has a next digit — the width is fixed.
Here, the sentinel bucket ∅ is deliberately excluded from
recursion: every word inside it is, by construction, exactly d characters long and
identical to every other word in the range up to that point, so two different words landing in
∅ together are already the same string. There's nothing left to compare, and
recursing into it anyway would call charAt past the end of an already-exhausted string
forever — see Pitfalls. Every other bucket (an actual letter) recurses only if it holds more than
one word, narrowing the range and moving one character position deeper each time.
That's also why this sort's recursion depth isn't fixed the way a digit-pass count is. A branch
where every word diverges by its second character stops recursing after two levels; a branch where a
hundred words all start with the same eight letters keeps recursing, doing real work at every one of
those eight levels before anything separates. Measured directly: 2,000 random 10-character words
examine only 61.3% of the character count a full-length scan of every word would cost
(they usually diverge within the first character or two, since the alphabet is far larger than any one
bucket's typical occupancy); the same 2,000 words forced to share an 8-character prefix examine
218.9% of that count instead — every one of those 8 levels does a full
count-then-place pass (two charAt calls per word) over the entire un-narrowed range before
finally reaching a level where the words differ. The algorithm adapts to how quickly keys become
distinguishable; it isn't guessing.
This is the exact scheme the demo above steps through, verified against
Array.prototype.sort across 30,000 random trials (including forced duplicates and
forced prefix relationships) with zero mismatches, plus a 50-identical-string stress case to confirm
the sentinel exclusion above actually prevents runaway recursion:
const R = 26; // lowercase a-z
// -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 msdStringSort(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
// count: two extra slots so -1 (sentinel) and R-1 ('z') both fit at count[c+2]
const count = new Array(R + 2).fill(0);
for (let i = lo; i <= hi; i++) count[charAt(a[i], d) + 2]++;
// map: prefix sum into start offsets, one array shift further than the count above
for (let r = 0; r < R + 1; r++) count[r + 1] += count[r];
// place: count[c+1] doubles as this bucket's next-open-slot locator
const aux = new Array(hi - lo + 1);
for (let i = lo; i <= hi; i++) {
const c = charAt(a[i], d);
aux[count[c + 1]++] = a[i];
}
for (let i = lo; i <= hi; i++) a[i] = aux[i - lo];
// recurse one character deeper into every real bucket (r = 0..R-1, never the sentinel)
for (let r = 0; r < R; r++) {
sort(a, lo + count[r], lo + count[r + 1] - 1, d + 1);
}
}
}The +2 in the count pass and +1 in the place pass aren't the same
offset by accident. count[r+1] gets read twice: once as bucket r's fixed
start offset (by the recursion loop, after every placement is done) and once as bucket
r's live "next open slot" locator (mutated in the place loop, the same
proxMap/locator split Proxmap sort's own reference
implementation keeps in two separate arrays). Here they deliberately share one array — by the
time bucket r's locator has advanced past every one of its own words, it has landed on
exactly the value bucket r+1 needs as its own start offset, so the recursion loop can
read the same, now-fully-advanced array safely, without ever allocating a second one.
Treating an exhausted word as "nothing to bucket" instead of routing it to the
sentinel silently drops data. It's tempting to special-case position d running
past a word's length by just skipping that word in both the count and place passes — after all, there's
no real character there. But skipping it means it's never written into the auxiliary array at all,
while every other word in the range still gets a slot. On ['sea', 'seashells', 'sells']
this produces ['seashells', 'seashells', 'sells'] — 'sea' vanishes
entirely and 'seashells' is duplicated into the slot 'sea' should have kept,
because the copy-back pass only overwrites a[i] where aux[i-lo] was actually
written, leaving 'sea''s original slot to be clobbered by whatever the next real bucket's
recursion writes there instead. Checked directly, not just on this one case: across 20,000 random
trials seeded to guarantee at least one prefix relationship per trial, this variant produced a wrong
result in 18,188 of them (90.9%), with silent data loss (a duplicated word standing in
for a vanished one) rather than a crash every time.
Forgetting to advance the character position on the recursive call is a stack
overflow, not a wrong answer. sort(a, lo + count[r], lo + count[r+1] - 1, d)
instead of d + 1 looks like a plausible typo rather than a logic error, but it means every
recursive call re-examines the exact same character position on a range that's already been narrowed
to share that character — the range never shrinks by even one word, and d never
increases, so the recursion has no base case it can ever reach. Run on this page's own default 10-word
demo array, it throws RangeError: Maximum call stack size exceeded every time, not a wrong
sort. Checked across 500 random trials with words 2–7 characters long: 208 of them
(41.6%) crashed outright with a stack overflow (any pair of words sharing a first character is
enough to trigger it); the remaining trials happened to have every word diverge from its neighbors
within the very first character, so no bucket ever held more than one word and the missing
+1 was never actually exercised. Nothing in between — it's either fully correct by
accident or a hard crash, never a silently wrong order.
Time: expected O(n logᵣR n), worst case O(n·w)
where w is the longest word's length. Every recursion level does O(range size)
work (two passes, count and place, over whichever words are still in that level's range), and the
number of levels any given word participates in is exactly how many leading characters it takes to
become the sole occupant of its own bucket. For random keys drawn from a large alphabet, that's
typically O(logᵣR n) characters — measured directly above at 61.3% of the
naive n·w character-examination count for 2,000 random 10-character words. Only
inputs with long shared prefixes push recursion toward the true O(n·w) worst case,
where every word participates in every one of the w levels before finally separating —
measured at 218.9% of n·w for 2,000 words sharing an 8-character prefix, the excess
over 100% coming from the count-then-place double pass each of those unproductive levels still has to
run. This is the concrete version of the same trade the site's non-comparison-sort guide already
frames as American flag sort versus radix sort's fixed d passes: fixed-width keys always
cost exactly d passes over everything, but variable-width string keys can cost anywhere
from close to one pass to the full key length, depending on how quickly the data actually
differs.
Space: O(n + R) per active recursion level — one
R+2-slot count array and one auxiliary array sized to that level's own range, both
discarded once that level returns. Recursion depth is bounded by w, the longest word in
the range still being distinguished, so total space across the whole call stack is
O(n + R·w) in the worst case: still no auxiliary array anywhere near
O(n) per character the way radix sort's fixed
per-pass buffer is, since only the words still sharing a prefix at a given depth ever occupy a
recursion level's arrays at once.
See Choosing a Non-Comparison Sort for how this compares against the site's other nine Non-Comparison Sorts entries — short version: reach for this over American flag sort or radix sort the moment the keys are strings that don't all share one fixed width, since both of those assume a well-defined digit exists at every position for every key and this is the one entry here that doesn't.