Worked examples — Radix sort — LSD, MSD; O(d(n+k))

The scenario matrix

Before touching a single number, let us list every distinct kind of situation a radix sort can face. If we cover one example per row, the reader never meets a case we skipped.

Symbols reused from the parent, restated so nothing is assumed:

• $n$ = how many elements we sort.
• $k$ = the radix = how many different values one digit can take (base 10 → $k=10$).
• $d$ = number of digit positions we must process $=\lceil {\log }_k(\max \text{ key})\rceil$.
• A digit-selector: for value $x$, digit at position $p$ (counting from 0 at the right) is $\left(\lfloor x/k^p\rfloor \right)\mathrm{mod}k$ — "chop off the low $p$ digits, then take the remainder mod $k$". We lean on Counting Sort for each pass and on Stability in Sorting to keep ties in order.

Ex 1 — Cell A: textbook LSD, base 10

Forecast: the answer must be the numeric sort $[329,355,436,457,657,720,839]$. Guess how many passes: max key is $839$ → 3 digits → 3 passes.

1. Pass $p=0$ (units). digits $9,7,7,9,6,0,5$. Stable counting sort → $[720,355,436,457,657,329,839]$. Why this step? We start at the least significant digit so that later, heavier digits can overwrite this ordering while stability protects the ties.
2. Pass $p=1$ (tens). digits of the current array: $2,5,3,5,5,2,3$ → $[720,329,436,839,355,457,657]$. Why this step? Among the three keys with tens-digit $5$ ($355,457,657$) the previous units order is preserved — that is stability doing the induction's job.
3. Pass $p=2$ (hundreds). digits: $7,3,4,8,3,4,6$ → $[329,355,436,457,657,720,839]$. ✅

Verify: compare to Python's sorted() of the same list — identical. Every key has 3 digits or fewer, so 3 passes were exactly $d=\lceil {\log }_{10}839\rceil =3$.

Ex 2 — Cell B: zero and short keys among long ones

Forecast: shorter numbers behave as if their missing high digits are zero. Answer should be $[0,7,9,88,105]$.

1. $d$? max $=105$ → 3 digits → 3 passes. Why this step? $\lfloor 0/k^p\rfloor \mathrm{mod}k=0$ for all $p$, and $\lfloor 9/100\rfloor =0$ — so "no digit there" is automatically read as digit $0$. Nothing special needed.
2. Pass $p=0$ (units): digits $0,9,5,7,8$ → $[0,105,7,88,9]$.
3. Pass $p=1$ (tens): digits $0,0,0,8,0$ → $[0,105,7,9,88]$. Why this step? $0,105,7,9$ all have tens-digit $0$ → they keep prior order (stability); $88$ goes last.
4. Pass $p=2$ (hundreds): digits $0,1,0,0,0$ → $[0,7,9,88,105]$. ✅

Verify: $0$ never moves relative to the other zero-high-digit keys except when a real higher digit appears — matches sorted([0,9,105,7,88]) = [0,7,9,88,105].

Ex 3 — Cell C: negative numbers

Forecast: $-42$ is the smallest, so the answer is $[-42,-5,-1,0,3,8]$. But $\lfloor -5/1\rfloor \mathrm{mod}10$ misbehaves — negatives need a fix.

1. The problem. Radix's digit extraction assumes non-negative integers. Why this step? If we naively took $(-5)\mathrm{mod}10=5$ in most languages that's fine, but the magnitude ordering is backwards for negatives: $-42$ has a bigger magnitude than $-5$ yet must sort earlier. Ordinary radix would place larger magnitudes later.
2. The offset trick. Find $m=\min =-42$. Add $|m|=42$ to every key, making all values $\ge 0$: $[37,45,41,42,50,0]$. Why this step? Shifting by a constant is order-preserving ($a<b⟺a+c<b+c$), so sorting the shifted keys sorts the originals — and now every value is non-negative, so plain LSD works.
3. LSD sort the shifted array ($d=2$, max $=50$): → $[0,37,41,42,45,50]$.
4. Subtract 42 back: $[-42,-5,-1,0,3,8]$. ✅

Verify: sorted([-5,3,-1,0,8,-42]) = [-42,-5,-1,0,3,8]. Offset in, offset out — bijection kept.

Ex 4 — Cell D: all keys equal (degenerate)

Forecast: the array is already sorted; every pass is a no-op; the index tags stay in order $a,b,c,d$.

1. Pass $p=0$: all units digits are $7$. Counting sort's prefix array sends them all to the same bucket. Why this step? The placement loop walks right to left and decrements, so $7_d$ lands after $7_c$ after $7_b$ after $7_a$ → order $a,b,c,d$ preserved.
2. Passes $p=1,2,\dots$: identical no-ops. Degenerate but correct.

Verify: stability means a totally-tied input comes out unchanged. Tags remain $[a,b,c,d]$ — stable_sort([7,7,7,7]) keeps original order. This is the boundary case that proves stability, not just "sorted correctly", matters for Stability in Sorting.

Ex 5 — Cell E: MSD on variable-length strings, early stop

Forecast: answer alphabetical: ["an","ant","at","az","zebra"]. And MSD should read very few characters of "zebra".

1. Char 0: buckets a={at, ant, an, az}, z={zebra}. Why this step? MSD splits on the most significant char; bucket z has one element → done immediately, reading only "zebra"[0]. That's the early-stop win.
2. Recurse bucket a on char 1: t→{at}, n→{ant, an}, z→{az}. Order so far by char 1: n-group, then t, then z. Why this step? Only bucket a is touched — MSD localizes work to the relevant slice.
3. Recurse {ant, an} on char 2: "an" has no char 2 (shorter) → treat "end of string" as smaller than any letter → an before ant. Why this step? Variable length: a key that ends sorts before one that continues, matching dictionary order ("an" < "ant").
4. Concatenate: ["an","ant","at","az","zebra"]. ✅

Verify: equals sorted(["zebra","at","ant","an","az"]). Characters read: zebra→1, at→2, ant→3, an→2 (ends), az→2. LSD would have scanned all 5 chars of zebra. MSD read 1 — the Tries-like prefix descent pays off.

Ex 6 — Cell F: choosing the radix

Forecast: more bits per digit → fewer passes but a bigger count array. Guess which wins for $n=10^6$.

1. $k=2^8=256$: bits per digit $=8$, so $d=\lceil 32/8\rceil =4$. Work $=d(n+k)=4(10^6+256)=4,001,024$. Why this step? Each pass processes one 8-bit slice; 32 bits ÷ 8 = 4 slices.
2. $k=2^{16}=65536$: bits per digit $=16$, so $d=\lceil 32/16\rceil =2$. Work $=2(10^6+65536)=2,131,072$. Why this step? Bigger $k$ halves the passes, and $k=65536\ll n=10^6$ so the count array is still cheap.
3. Compare: $2,131,072<4,001,024$ → $k=2^{16}$ wins here. Why this step? The rule $d(n+k)$ favours large $k$ as long as $k$ stays small relative to $n$. Since $65536\ll 10^6$, we pay almost nothing extra for the count array.

Verify: the two totals are $4001024$ and $2131072$; the second is smaller. (For tiny $n$, a huge $k$ would lose because $k$ dominates — this is the Big-O trade-off in $n+k$.)

Ex 7 — Cell G: limiting behaviour, huge keys

Forecast: the parent warned $d={\log }_k(\max )$ hides a $\log$. Guess: no, it becomes $O(n\log n)$-ish.

1. Compute $d$: $d=\lceil {\log }_k(\max )\rceil =\lceil {\log }_n(n^3)\rceil =3$. Why this step? ${\log }_n(n^3)=3$ exactly — choosing $k=n$ makes each digit "worth" a full factor of $n$, so only 3 digits are needed.
2. Total cost: $T=d(n+k)=3(n+n)=6n=O(n)$. Linear! ✅ Why this step? With $k=n$ the count array costs $O(n)$, same order as the data — no penalty.
3. The catch — what if we'd fixed $k=10$? Then $d={\log }_{10}(n^3)=3{\log }_{10}n=\Theta (\log n)$ and $T=\Theta (n\log n)$ — the Comparison Sort Lower Bound is matched, not beaten. Why this step? The linear result depends on scaling $k$ with $n$. A fixed small radix reintroduces the hidden logarithm.

Verify: ${\log }_n(n^3)=3$ (independent of $n$); $3(n+n)=6n$. And ${\log }_{10}(1000^3)=9=3{\log }_{10}1000$ confirms $d=\Theta (\log n)$ when $k$ is fixed.

Ex 8 — Cell H: word problem

Forecast: it's a 6-digit decimal key → LSD, base 10, 6 passes. Answer: chronological order.

1. Model the key. Treat HHMMSS as the integer $HHMMSS$ (e.g. 093045 → $93045$). Why this step? Lexicographic order of fixed-width digit strings equals numeric order, so sorting the integer sorts the times.
2. Choose LSD, $k=10$, $d=6$. Why this step? Fixed-width numeric keys are LSD's sweet spot (Cell A of the matrix, scaled up).
3. Cost: $T=d(n+k)=6(n+10)=O(n)$ for large $n$ — beats $O(n\log n)$ comparison sort. Why this step? $d=6$ and $k=10$ are constants, so linear time regardless of $n$.

Verify: for $n=1000$ orders, work $=6(1000+10)=6060$ basic ops — vs a comparison sort's $\approx n{\log }_{2}n=1000\times 10=10000$. Radix is fewer ops here, and every timestamp fits in 6 digits so 6 passes suffice.

Ex 9 — Cell I: exam twist, stability sabotage

Forecast: correct answer is $[11,12,21,22]$. An unstable pass can scramble ties on the tens digit. Guess: it breaks.

1. Pass $p=0$ (units), stable would give: units $1,1,2,2$ → keys with unit $1$: $21,11$ (order kept), unit $2$: $22,12$ → correct partial $[21,11,22,12]$… but suppose the unstable sort reorders ties → $[11,21,12,22]$ (units still grouped, but ties flipped). Why this step? An unstable sort may permute equal-key elements arbitrarily; that's allowed by its contract.
2. Pass $p=1$ (tens): tens digits of $[11,21,12,22]$ are $1,2,1,2$. Unstable again may output, among tens-$1$ group $\{11,12\}$ and tens-$2$ group $\{21,22\}$, e.g. $[12,11,22,21]$. Why this step? The lower-digit order from pass 0 is not protected — the induction in the parent proof required stability, and it's now gone.
3. Result: $[12,11,22,21]$ — not sorted ($12$ before $11$). ✗ Why this step? This is exactly the collapse the parent's "steel-man" warned about.

Verify: the correct output is sorted([21,11,22,12]) = [11,12,21,22]. Our unstable trace gives $[12,11,22,21]\ne [11,12,21,22]$, so unstable-per-digit radix is provably wrong. Stability is not optional.

Active Recall

Flashcards