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

$\exp =100$ picks the hundreds place. $(4729÷100)\mathrm{mod}10=47\mathrm{mod}10=7.$ What we did: integer-divided by $100$ to shift the hundreds digit down to the units slot, then took $\mathrm{mod}10$ to chop off everything above it. Answer: $7$.

$d=\lceil {\log }_{10}802\rceil =3$ (802 has three digits: units, tens, hundreds). The loop condition is $\text{maxv}÷\exp >0$, where maxv is the largest key in the array (here $802$) and $÷$ is integer division. It stays true for $\exp =1,10,100$ (giving $802,80,8$) and becomes false at $\exp =1000$ because $802÷1000=0$. So the loop body — one counting-sort pass — runs exactly three times. Answer: $d=3$ passes.

The prefix-sum count[d] holds the last index a key with digit $d$ may occupy. Walking right-to-left and decrementing count[d] before each placement puts the rightmost equal-digit element at the highest free slot — so equal-digit elements land in their original relative order. That is exactly stability, which the LSD correctness proof needs. (See the plum arrow in the bottom row of figure s01.) Answer: to preserve stability.

Step 1 — tally each units digit. Units digits are $3,9,0,6,3,3$. $\text{count}=[1,0,0,3,0,0,1,0,0,1](\text{indices }\mathrm{0..9}).$ So digit 0 appears once, digit 3 three times, digit 6 once, digit 9 once.

Step 2 — prefix sums → "last free slot". Replace each count[i] by the running total count[i] += count[i-1]. This tells us the index just past where digit $i$'s block ends: $\text{count}=[1,1,1,4,4,4,5,5,5,6].$ Read it as: digit 0 owns slot up to index 1 (slot 0), digit 3 owns up to index 4 (slots 1–3), digit 6 up to 5 (slot 4), digit 9 up to 6 (slot 5).

Step 3 — place right-to-left, decrementing first. We walk the input from the right so equal-digit elements keep their original order (stability):

• $233$ (d=3): count[3] $4\to 3$, place at index 3.
• $633$ (d=3): count[3] $3\to 2$, place at index 2.
• $36$ (d=6): count[6] $5\to 4$, place at index 4.
• $150$ (d=0): count[0] $1\to 0$, place at index 0.
• $89$ (d=9): count[9] $6\to 5$, place at index 5.
• $53$ (d=3): count[3] $2\to 1$, place at index 1.

Slots (0..5): $150,53,633,233,36,89$. Note $53,633,233$ landed in indices $1,2,3$ — their original left-to-right order preserved, exactly because we placed right-to-left.

Answer: $[150,53,633,233,36,89]$.

Pass $\exp =1$ (units). Units digits $9,7,7,9,6,0,5$. Tally: digit 0→1, 5→1, 6→1, 7→2, 9→2. Prefix sums give block ends $[1,1,1,1,1,2,3,5,5,7]$. Placing right-to-left: $[720,355,436,457,657,329,839].$ (Among the two digit-7 keys, $457$ then $657$ keep their input order because $657$, met first going right-to-left, takes the higher of the two digit-7 slots.)

Pass $\exp =10$ (tens). Tens digits of the current array $2,5,3,5,5,2,3$. Tally: 2→2, 3→2, 5→3. Prefix sums $[0,0,2,4,4,7,7,7,7,7]$. Placing right-to-left: $[720,329,436,839,355,457,657].$ Among the three tens-5 keys, the incoming order was $355,457,657$ (from the units pass), and the stable placement keeps exactly that — this is the units order riding along inside the tie.

Pass $\exp =100$ (hundreds). Hundreds digits $7,3,4,8,3,4,6$. Tally: 3→2, 4→2, 6→1, 7→1, 8→1. Prefix sums $[0,0,0,2,4,4,5,6,7,7]$. Placing right-to-left: $[329,355,436,457,657,720,839].✓$ Answer: $[329,355,436,457,657,720,839]$.

Here $T$ counts basic operations across all passes: each pass does $O(n)$ tally + $O(n)$ placement

• $O(k)$ prefix work $=(n+k)$ units of work, and there are $d$ passes, so $T=d(n+k)$. $d=\lceil {\log }_{10}999\rceil =3$. Then $T=d(n+k)=3(10^6+10)=3\times 1,000,010=3,000,030.$ Answer: $T=3,000,030$ basic operations.

The failure must involve a tie on the higher (tens) digit but a difference on the lower (units) digit — that's the only place stability does work. The smallest such pair is $[19,11]$: both have tens digit $1$ (the tie), units digits $9$ and $1$ (the difference).

• Units pass: digits $9,1$ → correct order is $[11,19]$.
• Tens pass: both tens digits are $1$ — a tie. A stable sort must keep $[11,19]$. A non-stable selection sort, seeing two "equal" tens digits, is free to swap them back to $[19,11]$ → wrong output $[19,11]$.

Answer: $[19,11]$ (any pair equal on the top digit, unequal on a lower digit) breaks a non-stable per-digit sort.

Char 0: d,c,c,d → buckets c={cat,cow}, d={dog,dot}. (4 reads) Bucket c char 1: a vs o → distinguishes immediately → [cat, cow]. (2 reads) Bucket d char 1: o vs o → tie → recurse char 2: g vs t → [dog, dot]. (2 + 2 reads) Total reads: $4+2+2+2=10$. Never read: cat[2]='t' and cow[2]='w' — bucket c was resolved at char 1, so char 2 of those two strings is never examined. Answer: 10 reads; cat[2], cow[2] skipped.

$d=\lceil 32/{\log }_{2}k\rceil$:

• $k=2^4$: $d=32/4=8$ passes, count array size $16$.
• $k=2^8$: $d=32/8=4$ passes, count array size $256$.
• $k=2^{16}$: $d=32/16=2$ passes, count array size $65536$.

$k=2^{16}$ minimises passes ($d=2$) but its count array of $65536$ entries dwarfs the data unless $n$ is huge; each pass also costs $O(n+k)$ so the $+k$ term ($65536$) becomes non-negligible. Answer: $d$ is smallest at $k=2^{16}$ ($d=2$); trade-off is a $65536$-slot count array vs the $256$-slot one at $k=2^8$.

Idea: shift all keys by a constant so the minimum becomes $0$, radix-sort, then shift back. Let $m=\min =-12$. Add $-m=12$ to every key: $[7,15,11,12,20,0]$ — all non-negative. Sort with ordinary LSD radix (max is $20$, base 10, $d=2$):

• units (digits $7,5,1,2,0,0$): stable placement gives $[20,0,11,12,15,7]$. (digit 0: $20,0$; digit 1: $11$; digit 2: $12$; digit 5: $15$; digit 7: $7$)
• tens (digits of $[20,0,11,12,15,7]$ are $2,0,1,1,1,0$): $[0,7,11,12,15,20]$.

Subtract $12$ back: $[-12,-5,-1,0,3,8]$. Answer: $[-12,-5,-1,0,3,8]$. (Shifting preserves order because it's monotonic.)

LSD radix's per-digit sort (counting sort) is stable, and the whole LSD chain preserves the relative order of keys equal on the sort field. So equal ages retain their input order — exactly the requirement, no extra work needed. Ages: $30,12,30,12$. Sorting stably by age:

• age 12: B, D (input order)
• age 30: A, C (input order)

Answer: [(12,"B"), (12,"D"), (30,"A"), (30,"C")].

Bucket sort groups by value range (e.g. $[0,0.1),[0.1,0.2),\dots$), then sorts inside each bucket with some comparison sort — one scatter pass, assuming uniform-ish data. Radix sort groups by a single digit value ($\mathrm{0..}k-1$), which only resolves ordering on that one digit; it needs $d$ passes (one per digit) to resolve the whole key, and relies on stability to chain the passes. Answer: bucket = group by value range (one pass); radix = group by one digit (needs $d$ stable passes to cover all digit positions).

Invariant. After the passes for digit positions $0,1,\dots ,i$ (least significant first), the array is sorted in non-decreasing order by the number formed from those low $i+1$ digits.

Base ($i=0$): we stably counting-sort by digit $0$; the array is now sorted by the lowest digit — the number "formed by digit 0" is just that digit. ✓

Inductive step. Assume the array is sorted by digits $\mathrm{0..}i$. Pass $i+1$ stably sorts by digit $i+1$. Take any two keys $x,y$ that appear in the output in order $x$ before $y$:

• Different digit $i+1$: the stable sort placed the smaller digit-$(i+1)$ key first, and the digit in position $i+1$ carries more place-value than all of positions $\mathrm{0..}i$ combined, so it dominates the value of the $(i+2)$-digit number — the order is correct.
• Equal digit $i+1$: stability keeps their previous relative order untouched; by the inductive hypothesis that order was already correct on digits $\mathrm{0..}i$, and since the top digit is equal, it stays correct on digits $\mathrm{0..}i+1$.

Both cases give the correct order, so the invariant holds for $i+1$. By induction it holds for all $i$; at $i=d-1$ every digit has been processed and the array is fully sorted. $■$

Answer: proof complete — the two-way case split (different vs equal higher digit) plus stability is the whole engine.

With $k=n$: $d=\lceil {\log }_n(n^c)\rceil =\lceil c\rceil =c$ (a constant). $T=O(d(n+k))=O(c(n+n))=O(c\cdot n)=O(n).$ This is linear whenever $c$ is a fixed constant, so radix beats $O(n\log n)$ for every constant $c$ (any polynomially-bounded key range). It loses only when keys grow faster than any polynomial (e.g. $\max =2^n$, giving $d=\Theta (n)$). Answer: $d=c$, $T=O(cn)=O(n)$; radix wins for all constant $c$. This dodges the Comparison Sort Lower Bound because radix never compares whole keys.

Treat "no more characters" as a special bucket that sorts before every real character (shorter-prefix comes first lexicographically):

def msd(strings, pos):
    if len(strings) <= 1: return strings
    buckets = {}          # key: char at pos, or END sentinel
    for s in strings:
        key = END if pos >= len(s) else s[pos]
        buckets.setdefault(key, []).append(s)
    result = []
    for key in sorted(buckets):        # END first, then 'a'..'z'
        group = buckets[key]
        result += group if key is END else msd(group, pos+1)
    return result

Trace on ["an","ant","and","a"], pos 0 (all start a) → recurse pos 1:

• a → END (len 1) : ["a"]
• an,ant,and → char 1 = n : recurse pos 2:
  • an → END : ["an"]
  • ant char 2 = t, and char 2 = d → d < t → ["and","ant"]

Concatenate END-first: ["a", "an", "and", "ant"]. Answer: ["a", "an", "and", "ant"]. The END sentinel (sorting first) is what makes a prefix precede its extensions — the same trick Tries use for word boundaries.

Digit at $\exp =100$ of $4729$ ::: $7$ Passes for max key $802$, base 10 ::: $3$ $T$ for keys in $[0,n^c]$ with $k=n$ ::: $O(n)$, since $d=c$ Input breaking a non-stable per-digit sort ::: $[19,11]$ (tie on tens digit) Sentinel that makes "an" < "ant" in MSD ::: END, sorted before every character