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

WHAT is Radix Sort?

Key vocabulary:

• $n$ = number of elements.
• $k$ = the radix / number of possible digit values (e.g. $k=10$ for decimal, $k=256$ for bytes).
• $d$ = number of digit positions = $\lceil \log_k(\text{max key}) \rceil$.

WHY does LSD radix sort work? (Derivation from scratch)

We need an invariant. Claim:

After processing digit positions $0,1,\dots,i$ (least significant first), the array is sorted by the number formed by those low $i+1$ digits.

Proof by induction.

Base case ($i=0$): we stably sort by digit 0. The array is sorted by the lowest digit. ✓

Inductive step: Suppose after pass $i$ the array is sorted by digits $0..i$. In pass $i+1$ we stably sort by digit $i+1$.

• Two keys with different digit $i+1$ end in the correct relative order, because the higher digit dominates the value.
• Two keys with the same digit $i+1$ keep their previous relative order — because the sort is stable — and that previous order was already correct on digits $0..i$. ✓

So after all $d$ passes the array is fully sorted. ∎

HOW: the algorithm (LSD with counting sort per digit)

def lsd_radix(a, k=10):
    if not a: return a
    maxv = max(a)
    exp = 1                       # 1, k, k^2, ...  selects the digit
    while maxv // exp > 0:        # loop runs d times
        a = counting_sort_by_digit(a, exp, k)
        exp *= k
    return a

def counting_sort_by_digit(a, exp, k):
    n = len(a)
    out = [0]*n
    count = [0]*k
    for x in a:                       # 1) tally this digit
        count[(x // exp) % k] += 1
    for i in range(1, k):             # 2) prefix sums -> end positions
        count[i] += count[i-1]
    for x in reversed(a):             # 3) place RIGHT-to-LEFT => STABLE
        d = (x // exp) % k
        count[d] -= 1
        out[count[d]] = x
    return out

WHY the running time is $O(d(n+k))$ (Derivation)

One counting-sort pass costs:

• tally loop: $O(n)$
• prefix-sum loop: $O(k)$
• placement loop: $O(n)$

So one pass $= O(n+k)$. We do exactly $d$ passes.

$\boxed{T(n) = d \cdot O(n+k) = O\big(d(n+k)\big)}$

When is this beating $O(n\log n)$? If keys are bounded so $d$ is constant (e.g. 32-bit ints with $k=2^8$ ⇒ $d=4$) and $k=O(n)$, then $T=O(n)$ — linear.

MSD vs LSD

Worked Example 1 — LSD on $[170, 45, 75, 90, 802, 24, 2, 66]$, base 10

Pass exp=1 (units digit): digits → 0,5,5,0,2,4,2,6. Stable counting sort gives [170, 90, 802, 2, 24, 45, 75, 66]. Why this step? We sort by the least significant digit first so later passes (which dominate) can rely on stability to preserve this order among ties.

Pass exp=10 (tens digit): digits → 7,9,0,0,2,4,7,6 → [802, 2, 24, 45, 66, 170, 75, 90]. Why this step? Among keys with equal tens digit (170 & 75 both have tens 7) the previous unit order is preserved by stability.

Pass exp=100 (hundreds digit): digits → 8,0,0,0,0,1,0,0 → [2, 24, 45, 66, 75, 90, 170, 802]. ✅ Sorted. Why this step? Max value 802 has 3 digits, so $d=3$ passes suffice; after the top digit the array is fully ordered.

Worked Example 2 — MSD on strings ["bat","apple","ant","bad"]

Sort by char 0: bucket a = {apple, ant}, bucket b = {bat, bad}. Why this step? The most significant character splits the data; buckets are independent.

Recurse in bucket a on char 1: both have n/p... actually "apple"[1]=p, "ant"[1]=n → ant before apple. Bucket a = [ant, apple]. Why this step? Only these two elements are touched — MSD localizes work.

Recurse in bucket b on char 1: "bat"[1]=a, "bad"[1]=a (tie) → recurse char 2: d < t → [bad, bat]. Why this step? We descend only as deep as needed to break ties.

Concatenate: [ant, apple, bad, bat]. ✅

Worked Example 3 — choosing the radix for 32-bit ints

Keys up to $2^{32}-1$. Choose $k=2^{8}=256$ (sort one byte per pass). $d = 32/8 = 4$ passes. Cost $= 4(n + 256) = O(n)$ for large $n$. Why this step? Bigger $k$ → fewer passes ($d=\lceil 32/\log_2 k\rceil$) but bigger count array. $k=256$ balances both; the count array (256 ints) is negligible vs $n$.

Active Recall

Flashcards

Connections

• Counting Sort — the stable engine inside each radix pass.
• Comparison Sort Lower Bound — the $\Omega(n\log n)$ wall radix sidesteps.
• Stability in Sorting — the property the correctness proof relies on.
• Bucket Sort — cousin that distributes by value range instead of by digit.
• Big-O Notation — interpreting $O(d(n+k))$ and the hidden $\log$.
• Tries — MSD radix sort is essentially building a trie level by level.

Concept Map

Hinglish (regional understanding)