↩ back to Non-Comparison Sorts
An eleventh non-comparison sort, and the mirror image of MSD String Sort: both apply radix sort's and American flag sort's per-position counting-sort idea
to string keys instead of numbers, just from opposite ends. Radix sort's digit passes always find a
well-defined digit at every position because any number can be thought of as left-padded with
leading zeros to a common width for free — 5 and 500 already behave
as 005 and 500 the moment a fixed pass count is chosen. Strings have no
equivalent convention: "cat" isn't secretly the same length as
"category" with silent padding, so a pass keyed by "the character three from the
right" simply doesn't exist for the shorter word unless every key is already the same length. This
entry takes that constraint head-on rather than working around it the way MSD string sort does:
given keys that are genuinely, exactly the same length, run radix sort's exact three-pass count
→ prefix-sum → place scheme once per character position — 26 buckets instead of 10
digits — starting from the rightmost character and working left, the same direction and the
same reason radix sort's own digit passes must start from the ones digit.
Enter a comma-separated list of lowercase words (letters a–z
only). This demo requires every word to be exactly the same length — the
precondition the whole algorithm depends on — and Load rejects the input rather than silently
guessing what you meant if they don't match. Step through each character-position pass, rightmost
first: the array is counted into 26 letter-buckets, those counts become a
running total, then each word is placed into this pass's output,
scanned right-to-left. The array after each pass becomes the input to the next pass, working from
the last character toward the first.
The argument is the identical induction radix
sort's own "why it works" section makes, with characters standing in for digits and a
26-letter alphabet standing in for base 10. Every pass is a stable counting sort, so after the rightmost-character
pass, any two words that share that last character are already in the right relative order
with respect to that character. When the next pass over the second-to-last character
runs, words sharing that character keep whatever order they already have — their correct
order by last character, since that's what the previous pass produced. By induction, after
processing position d, the array is correctly sorted with respect to every character
from d to the end taken together. Once the leftmost pass finishes, the whole array is
sorted by the full key. Try it above on the default words: leap and
peal are anagrams of each other, so they only separate once the pass reaches a
position where their letters actually differ (position 1: e vs e is tied
so it isn't there — watch the log to see exactly which pass finally tells them apart).
This is also why the constraint on the "Try it" input isn't a demo limitation, the way the
14-character cap on MSD string sort's own
demo is — it's the whole algorithm's precondition. Radix sort gets a well-defined digit at
every position for free, because a number's "missing" leading digits really are zero. A string's
"missing" trailing characters aren't secretly some sentinel value every pass already knows how to
bucket — there's nothing at "cat".charCodeAt(5) to count. MSD string sort solves
that by inventing a real bucket for "nothing here yet" and excluding it from recursion; this entry
simply requires the problem not to exist in the first place, in exchange for radix sort's simpler,
non-recursive three-pass shape. See Pitfalls for exactly what happens if that requirement is
violated anyway.
This is the exact scheme the demo above steps through, verified against
Array.prototype.sort across 30,000 random same-length-word trials (word lengths 1
through 7, up to 10 words each) with zero mismatches:
const R = 26; // lowercase a-z
function charAt(word, d) { return word.charCodeAt(d) - 97; }
// every word in `words` must already be exactly the same length
function lsdStringSort(words) {
if (words.length === 0) return [];
const W = words[0].length;
let a = words.slice();
for (let d = W - 1; d >= 0; d--) { // rightmost character first
const buckets = new Array(R).fill(0);
for (const w of a) buckets[charAt(w, d)]++; // count
for (let b = 1; b < R; b++) buckets[b] += buckets[b - 1]; // prefix sum
const output = new Array(a.length);
for (let i = a.length - 1; i >= 0; i--) { // place, right to left
const c = charAt(a[i], d);
output[--buckets[c]] = a[i];
}
a = output;
}
return a;
}Character for character, this is radix sort's own reference
implementation with Math.floor(v / place) % 10 replaced by
charCodeAt(d) - 97 and 10 digit-buckets replaced by 26 letter-buckets. Nothing else
about the count → prefix-sum → place shape, or the right-to-left placement order, changes
at all — the only thing that changed is what a "digit" means.
The fixed-width requirement is load-bearing, not a suggestion — violating it
doesn't sort wrong, it crashes. A direct-but-naive port of the reference implementation
above, computing W as the longest word's length instead of validating every
word already matches, looks like it should degrade gracefully: charCodeAt(d) on a
shorter word just returns NaN past its own end, and a bucket index of
NaN is easy to imagine getting silently ignored. It doesn't get ignored cleanly. On
the very first pass, a word that's too short to have a real character at position d
never gets counted and never gets placed — it simply vanishes, leaving an empty
(undefined) slot in that pass's output. The next pass then calls
charCodeAt on that empty slot directly, which throws
TypeError: Cannot read properties of undefined (reading 'charCodeAt') rather than
producing any sorted order at all. Smallest hand-checkable case: ['a', 'ba', 'ab'].
The rightmost-character pass (position 1) buckets 'ba' and 'ab' normally
but drops 'a' entirely (no character at position 1), leaving
['ba', 'ab', undefined]; the very next pass (position 0) crashes trying to read
undefined.charCodeAt(0). Checked broadly, not just this one case: across 20,000
random trials with word lengths 1–6, every single trial where the lengths actually differed
(19,507 of 20,000) crashed this way — 100%, zero of them produced a
silently wrong order instead. The remaining trials happened to draw same-length words by chance and
sorted correctly, same as the validated version above.
Passes have to start from the rightmost character and work left — running them
in reading order breaks the induction the moment two words tie on an early character. It's
a tempting mistake specifically for strings, more than for radix sort's digits: people read words
left to right, so "sort by the first character, then the second" feels like the natural order,
even though radix sort's own first pitfall
already establishes that a later stable pass can only preserve ties an earlier pass created, never
the other way around. Run the passes most-significant-character first instead of least, and the
last pass to run (over the final character) is free to reshuffle ties on every earlier,
more important character it never even looks at. Hand-checkable: sorting
['ba', 'bb', 'ab'] correctly (position 1, then position 0) gives
['ab', 'ba', 'bb']; running position 0 first, then position 1, gives
['ba', 'ab', 'bb'] instead — the first-character pass correctly separates
'ab' from the two 'b...' words, but the second-character pass that runs
afterward freely reorders 'ba' ahead of 'ab', since it never looks at the
first character it's supposed to be subordinate to. Checked broadly: across 20,000 random trials of
same-length words (lengths 2–7), running passes in reading order produced a wrong final
order 92.9% of the time.
Time: O(W·(n+R)) — W character-position
passes, each an O(n+R) counting sort with R=26 fixed. Unlike MSD string sort's own recursion, which
adapts to how quickly keys actually diverge (measured there at 61.3% of a full-length scan on
random words, up to 218.9% when words share a long prefix), this algorithm has no early exit at
all: every one of the W passes runs over the entire array unconditionally,
whether the words separate on their very first character or share every character but the last.
That's the direct trade for giving up recursion — a simpler, flatter shape that costs exactly
W·n character examinations every time, never less, never more.
Space: O(n+R) per pass — a 26-slot bucket array plus an
n-slot output array, both discarded and reallocated fresh each pass — identical
to radix sort's own space profile, since this
is the same algorithm over a different alphabet. Total space never exceeds one pass's worth at a
time, unlike MSD string sort's recursion stack, which holds one count array and one auxiliary array
per active recursion depth simultaneously.
See Choosing a Non-Comparison Sort for how this compares against the site's other ten Non-Comparison Sorts entries — short version: reach for this over MSD string sort only when every key is already exactly the same length; reach for MSD string sort the moment that's not guaranteed, since this one has no fallback for it at all (see Pitfalls).