WHAT. Take the number 170. In base 10 it is written with three slots:
hundreds1tens7units0
Each slot holds one digit: a symbol from 0 to 9. The radix (base) k is just how many
symbols are allowed in a slot — here k=10.
WHY. Sorting the whole number at once means comparing 170 against 45 against 802… which is
what quicksort does. Radix sort refuses to do that. Instead it looks at one slot for the whole
array, then the next slot, then the next. The bet: if we handle slots in the right order, the
number falls into place without ever comparing two full numbers.
PICTURE. The number as a row of slots, each with a place value underneath it. The accent-red
slot is the one slot we will sort by first — the units slot.
WHAT. For a single chosen slot we use Counting Sort: set up ktrays labelled
0,1,…,k−1, drop each number into the tray matching its digit in that slot, then scoop trays
up in order 0→k−1.
WHY this tool and not a comparison sort? Because a digit is a small integer in a known range
0..k−1. When the thing you sort by is a bounded integer, you don't need to compare — you can
index directly into a tray. Indexing is O(1); comparing costs a branch every time. This is the
whole reason radix escapes the Ω(nlogn) wall of a comparison sort.
PICTURE. The array [170,45,75,90,802,24,2,66] raining down by units digit into ten
trays. The red arrow follows one element, 45, into tray 5.
Scooping trays 0→9 left-to-right gives:
[170,90,802,2,24,45,75,66]
Now sorted by units digit only — but notice the tens/hundreds are still scrambled. That's fine;
one slot at a time.
WHAT.Stable means: when two elements have the same digit in the
current slot, the sort keeps them in the order they already had. It never reshuffles ties.
WHY it will matter. In Step 2, both 170 and 90 landed in tray 0 (units digit 0). Because
170 appeared before90 in the input, a stable pass keeps 170 before 90 inside tray 0. In
later passes, this "don't disturb ties" rule is exactly what preserves all the work done by earlier
passes. Hold that thought — Step 5 makes it the hero.
PICTURE. Two elements sharing a tray. A stable pass (top) keeps their order; an unstable pass
(bottom) swaps them — the red cross marks the damage.
WHAT. Counting sort computes, for each digit, the last index that digit is allowed to occupy
(via prefix sums). Then it walks the input from the rightmost element backward, and for each
element writes it at that last free slot and decrements the counter.
WHY. Suppose two elements share a digit d and get a block of, say, positions 3 and 4.
Walking from the right, the element that came later in the input is placed first — into the
higher position (4). The earlier one lands in position 3. So earlier-in-input ends up
earlier-in-output: stability, for free, from the reverse walk.
PICTURE. The prefix-sum array points at the end of each digit's block. Two red numbers sharing a
digit are placed back-to-front, preserving their original order.
WHAT. Here is the claim the whole algorithm rests on:
After we finish the pass on slot i (counting units as slot 0), the array is sorted by the number
formed by slots 0 through i — the low i+1 digits.
WHY it holds — the inductive picture. Say it's true after slot i. Now we stably sort by slot
i+1:
Different slot-(i+1) digits → the bigger digit means the bigger number, and the pass puts
them in that order. Correct. ✓
Same slot-(i+1) digit → the pass leaves them in the order they had, which (by our assumption)
was already correct on slots 0..i. Stability carries the old truth forward. ✓
So each pass extends "sorted by the low digits" one slot higher. After all d slots, the whole number
is sorted.
PICTURE. Two elements 170 and 75. Both have tens digit 7 (a tie). The red
strip shows their units order — set in Pass 1 — surviving untouched through Pass 2 because the tie is
preserved. That surviving strip is the induction hypothesis in action.
\;\xrightarrow{\text{stable sort by tens (slot }1)}\;
\underbrace{[802,\,2,\,24,\,45,\,66,\,170,\,75,\,90]}_{\text{sorted by tens+units (slots }0,1)}$$
Look at $170$ then $75$: same tens digit $7$, and $170$'s units ($0$) < $75$'s units ($5$), so $170$
correctly stays before $75$. Nobody compared them — stability did it.
---
## Step 6 — Watch all $d$ passes finish the job
**WHAT.** Run the last pass on the hundreds slot.
$$\underbrace{[802,\,2,\,24,\,45,\,66,\,170,\,75,\,90]}_{\text{slots }0,1\text{ sorted}}
\;\xrightarrow{\text{stable sort by hundreds}}\;
\underbrace{[2,\,24,\,45,\,66,\,75,\,90,\,170,\,802]}_{\text{fully sorted}}$$
**WHY it's now done.** The biggest key is $802$, which has $3$ digits, so
$d = \lceil \log_{10} 802 \rceil = 3$ passes. Once the *top* slot is sorted and all lower slots were
already correct among ties, the entire number is ordered. No more slots exist to fix.
**PICTURE.** The array snapshot after each of the three passes, stacked, with the red column marking
which slot that pass sorted — showing order "growing" leftward until the whole row is sorted.
![[deepdives/dd-coding-3.6.07-d2-s06.png]]
---
## Step 7 — Edge & degenerate cases (never leave the reader stranded)
**WHAT & WHY, case by case.**
- **Empty array** $[\,]$: `max` is undefined, so the code returns immediately — $0$ passes, correctly
"sorted".
- **One element** $[42]$: already sorted; loop still runs $d$ times but every pass leaves it put.
- **All equal** $[7,7,7]$: every element shares every digit → every pass is one big tie → stability keeps
them as-is. Output = input. Correct.
- **Different digit-counts** $[5, 802]$: shorter numbers have *implicit leading zeros*
($5 = 005$). Digit $0$ in a high slot just means "goes to tray $0$", so small numbers naturally sort
before large ones. The loop condition `maxv // exp > 0` runs $d$ passes based on the **largest** key,
which is exactly enough slots for everyone.
- **A zero key** $[0, 3]$: $0$ has digit $0$ in every slot — it lands in tray $0$ every pass and ends
up first. Correct.
**PICTURE.** $5$ padded to $005$ next to $802$; the red leading zeros show why a short key sorts low
without any special code.
![[deepdives/dd-coding-3.6.07-d2-s07.png]]
> [!mistake] "Numbers with fewer digits will break the passes."
> **Why it feels right:** $5$ has no hundreds digit. **Why it's wrong:** $(5 / 100)\bmod 10 = 0$ — the
> formula *manufactures* a $0$ for missing slots. Leading zeros are free. No padding code needed.
---
## The one-picture summary
**WHAT.** One diagram compresses the whole derivation: input at the top, three stable counting-sort
passes (units → tens → hundreds), the *sorted region growing leftward* after each, ending fully sorted.
The red thread traces the invariant surviving each pass.
![[deepdives/dd-coding-3.6.07-d2-s08.png]]
$$\boxed{\,T = O\big(d\,(n+k)\big)\,}\quad
\begin{aligned}
&d \text{ passes, each } O(n+k):\\
&\;n \text{ to tally + } k \text{ prefix sums + } n \text{ to place.}
\end{aligned}$$
- $d$ ::: number of digit slots $= \lceil \log_k(\max) \rceil$ — how many passes.
- $n$ ::: elements — the tally and placement loops.
- $k$ ::: trays — the prefix-sum loop over the count array.
> [!recall]- Feynman — the whole walkthrough in plain words
> You've got a messy stack of number-cards. You set out ten trays, $0$ to $9$. **Round 1:** look only
> at each card's *last* digit and drop it in the matching tray; when two cards want the same tray, the
> one you saw first goes in first. Scoop the trays up, $0$ then $1$ then… now they're sorted by last
> digit. **Round 2:** do the exact same thing by the *middle* digit — and here's the magic: whenever two
> cards tie on the middle digit, your "first-seen-first-in" rule keeps them in the last-digit order you
> already made, so that earlier work never gets wrecked. **Round 3:** repeat by the *first* digit. After
> as many rounds as the longest number has digits, the stack is perfectly sorted — and you never once
> held two whole cards side by side to compare them. Short numbers just have invisible leading zeros, so
> they quietly float to the front. That "keep ties in place" habit (**stability**) is the one rule that
> makes the whole trick work.
> [!recall] Test yourself
> 1. Why does placing right-to-left give a stable pass? ::: The prefix sum marks each digit's *last* slot; walking from the right fills it top-down, so earlier-in-input lands earlier-in-output.
> 2. What does the invariant say after finishing slot $i$? ::: The array is sorted by the number formed by the low $i{+}1$ digits (slots $0..i$).
> 3. Why do fewer-digit numbers not need special handling? ::: Integer division supplies a $0$ digit for missing high slots, so they sort into tray $0$ automatically.
> [!mnemonic]
> **Grow-Left**: each stable pass extends the sorted region one slot to the **left**, from units up to the top digit.
Related: [[Counting Sort]] · [[Stability in Sorting]] · [[Comparison Sort Lower Bound]] · [[Big-O Notation]] · [[Bucket Sort]] · [[Tries]]
