↩ back to Non-Comparison Sorts
Radix sort, on this site, works from the
least significant digit up, and leans on every pass being stable: sort by the ones
digit, then the tens digit, and stability guarantees the ones-digit order survives underneath. That
trick buys correctness without ever looking more than one digit at a time, but it costs an
O(n+k) auxiliary output array, rebuilt fresh every pass. American flag sort takes the
opposite route: work from the most significant digit down, and instead of writing to
a fresh array, count how many values belong in each digit-bucket first, fix each bucket's
final index range in advance, then permute the array in place — swapping every value
directly into its bucket, following the swap chain until everything lands. Ties within one bucket
aren't resolved yet, so it isn't stable; it recurses into the next (less significant) digit within
each multi-element bucket to finish the job, the same divide-and-conquer shape as
quicksort's partition, just ten-way instead of two-way.
Enter a comma-separated list of non-negative integers, each 0–99 (this demo fixes the width
at two digits — tens, then ones — and caps it at 10 values). Step through: for the active range,
each value is counted into a digit bucket, those counts become each bucket's
start/end boundary, then the range is permuted in place — bucket by
bucket, following each swap chain until every slot in that bucket holds a value that belongs there.
Any bucket left with more than one element then recurses on the ones digit. The
shaded region is the active range (reusing quicksort's
.partition window); the bordered bar is the index currently being examined; the solid
bar is its swap partner; settled bars are done for good.
The counting pass over a range [lo..hi] tells you exactly how many values have each
digit 0–9 at the current place, before anything moves. Turning those
counts into a running total, offset by lo, gives every bucket b a fixed
[starts[b], ends[b]) — the exact index range it will occupy once the permutation is
done, decided in advance rather than discovered by appending to a growing output. That's what makes
the in-place trick possible: since the destination range is already known, each value can be swapped
directly to a slot inside its own bucket's range instead of a separate array. The permutation walks
each bucket b with a cursor starting at starts[b]: if the value sitting there
already belongs in bucket b, advance the cursor; otherwise swap it with whatever sits at
its own bucket's cursor, and advance that bucket's cursor instead. Crucially, the
current index is not advanced after a foreign swap — the value that just arrived
might belong somewhere else too, and has to be checked again before moving on. Follow that chain of
swaps far enough and it always closes: every swap places at least one more value in its final bucket,
so after at most hi-lo+1 swaps every index in the range holds a value whose current digit
matches its bucket.
Grouping by one digit isn't the same as being sorted by it, though — unlike radix sort's stable passes, nothing here preserves relative order within a bucket, so a bucket with more than one element is grouped correctly but internally unordered. That's why the recursion is not optional the way an LSD pass's later stability is: any bucket holding two or more values must recurse on the next digit down before the range counts as sorted. Once the least significant digit (ones, for this fixed two-digit demo) has been processed for a range, every value in it has been distinguished by both digits, so there's nothing left to break a tie — the range is done.
Fixed two-digit width (base 10), matching the demo above exactly. place starts at
10 (tens) and divides by 10 each recursion until it drops below 1:
function americanFlagSort(arr, lo = 0, hi = arr.length - 1, place = 10) {
if (hi - lo < 1 || place < 1) return arr; // 0 or 1 elements, or no digits left
const counts = new Array(10).fill(0);
for (let i = lo; i <= hi; i++) counts[digit(arr[i], place)]++;
const starts = new Array(10);
const ends = new Array(10);
let acc = lo;
for (let b = 0; b < 10; b++) {
starts[b] = acc;
acc += counts[b];
ends[b] = acc; // exclusive
}
const next = starts.slice(); // per-bucket write cursor
for (let b = 0; b < 10; b++) {
while (next[b] < ends[b]) {
const idx = next[b];
const d = digit(arr[idx], place);
if (d === b) { next[b]++; continue; } // already in its bucket
[arr[idx], arr[next[d]]] = [arr[next[d]], arr[idx]]; // swap into its real bucket
next[d]++;
}
}
if (place > 1) {
for (let b = 0; b < 10; b++) americanFlagSort(arr, starts[b], ends[b] - 1, place / 10);
}
return arr;
}
function digit(v, place) {
return Math.floor(v / place) % 10;
}The in-place permutation must follow each swap chain, not just walk the range once.
It's tempting to write the permutation as a plain for loop over each bucket's index range
— advance idx unconditionally after handling it, the way a normal array scan works. That
breaks it: when arr[idx] gets swapped out for a foreign value pulled from later in the
array, that newly-arrived value might also not belong in bucket b, and a plain
loop that always moves on to idx+1 never checks it again. Run for real on
[75, 86, 61, 25]: the correct algorithm above produces [25, 61, 75, 86]; the
same code with the cursor-based while replaced by a fixed for (idx = starts[b];
idx < ends[b]; idx++) loop produces [61, 25, 75, 86] — still grouped into the
right tens-buckets, but 61 and 25 never got swapped past each other because the second one arrived at
an index the loop had already moved past. Checked broadly, not just this one case: over 5,000 seeded
random trials, the fixed-loop version disagrees with a correct sort on 2,054 of them (roughly 41%) —
not a rare edge case, a coin flip.
Skipping the recursion into the next digit leaves buckets grouped but not sorted.
The demo's own default array, [70, 91, 45, 24, 92, 12, 75, 3], groups correctly into
tens-buckets after just the tens-digit pass — but bucket 9 holds 91 and 92
in whatever order the swap chain happened to leave them, and bucket 7 holds 70 and
75 the same way. Running only the tens-digit pass and stopping there (no ones-digit
recursion) on this exact array produces [3, 12, 24, 45, 70, 75, 92, 91] — every other
value in its right place, but 91 and 92 swapped, because nothing after the first pass ever compared
them by their ones digit. Checked broadly: over the same 5,000 seeded trials, stopping after one pass
disagrees with a correct sort on 2,379 of them (roughly 48%). Unlike radix sort, where every pass is required by construction (each
digit position must be visited once, in order, or the stability chain breaks), here the recursion
depth genuinely varies per bucket — a bucket that happens to land with 0 or 1 elements is already
done and never recurses at all, which is real, exploitable savings when the input is already
partially sorted by its leading digits, not just an implementation detail to skip carelessly.
Only works directly on fixed-width, non-negative keys, same restriction as
radix sort. This demo fixes every key at exactly
two digits (0–99) so digit(v, 10) and digit(v, 1) always land in
[0, 9]; variable-width keys need padding to a common width first (extra leading zero
digits, conceptually), or the shorter keys sort as if their missing high digits are 0 — which is
usually what's wanted, but has to be deliberate, not assumed. Negative values need the same offset
trick radix sort's own Pitfalls section describes.
Time: O(d·(n+k)) — the same shape as
radix sort: d digit levels, each level's total
work across all its buckets bounded by O(n+k) (one full range scanned for counting, plus
one full range permuted, plus k=10 buckets' worth of bookkeeping). Space:
the real difference from radix sort — O(k) per active recursion level (just the counts,
starts, ends and cursor arrays, ten entries each) instead of a fresh O(n+k) output array
per pass, because every swap happens directly inside the input array. Recursion depth is at most
d, so total extra space is O(k·d), a constant for fixed-width keys —
genuinely smaller than radix sort's per-pass O(n) buffer, paid for by giving up
stability and, per the first Pitfall above, a permutation step that's easy to get subtly wrong.
See Choosing a Non-Comparison Sort for how this compares against the site's other nine Non-Comparison Sorts entries — short version: this one when memory is tighter than time and nothing depends on tie order surviving.