Radix Sort

A radix is the base of a number system, and radix sort treats each key as a sequence of d digits (or characters) each drawn from an alphabet of size k, for example base-10 digits (k = 10) or bytes (k = 256). The least-significant-digit (LSD) variant processes digit positions in order from the rightmost (least significant) to the leftmost (most significant), performing one full pass over the array per digit position. The subroutine used at each digit position must be a stable sort: a sort that never reorders two elements whose keys (at the digit being examined) are equal. Stability is the load-bearing property of the entire algorithm. Counting Sort is the canonical choice because it is stable by construction and runs in Θ(n + k) time and space, making the whole pipeline linear in each pass. Formally, radix sort is not a new sorting primitive at all — it is a reduction that turns the hard problem of sorting n composite keys into d easy problems of sorting n single-digit keys, glued together by the algebraic guarantee that stability provides. The alternative, most-significant-digit (MSD) radix sort, processes digits from left to right and recursively buckets elements into groups that share a prefix, similar in spirit to quicksort's partitioning. MSD can short-circuit on already-distinguished prefixes and is more natural for variable-length strings, but it needs auxiliary bucketing recursion and careful handling of unequal-length keys. LSD radix sort is simpler, requires only fixed-length (or padded) keys, and is the version whose correctness proof and complexity are cleanest — the focus of this article.

Fix keys of exactly d digits, digit positions numbered 0 (least significant) through d−1 (most significant), each digit in the range [0, k−1]. LSD radix sort makes d passes over the array; pass i stably sorts the entire array by digit i alone, using the current array order (the result of all previous passes) as the tie-breaker for equal digits.

Step-by-step: 1. Determine d, the maximum number of digits among all keys (pad shorter keys with leading zero-digits conceptually — this does not change their order). 2. For i = 0, 1, 2, …, d−1 (least significant digit first): a. Extract digit i from every key. b. Run a stable counting sort of the whole array using these extracted digits as the sort key. c. Replace the array with the sorted output; proceed to the next digit. 3. After the pass on digit d−1 (the most significant digit), the array is fully sorted. Why does going least-significant-first work, when intuitively you might sort by the "most important" digit first? The trick is that stability lets later (more significant) passes silently preserve the correct relative order established by earlier (less significant) passes whenever the more significant digits tie. Each pass only needs to get its own digit right and trust the sort to leave everything else alone when there's a tie — and that trust is exactly what stability provides. ``` RADIX-SORT(A, d, k) // A[1..n] : array of keys, each with exactly d digits in base k // digit(x, i) returns the i-th digit of x, i = 0 is least significant for i = 0 to d - 1 A = COUNTING-SORT-BY-DIGIT(A, i, k) return A COUNTING-SORT-BY-DIGIT(A, i, k) n = A.length output = new array of size n count = new array of size k, initialized to 0 // 1. Tally how many keys have each digit value for j = 1 to n d_j = digit(A[j], i) count[d_j] = count[d_j] + 1 // 2. Prefix-sum: count[v] becomes the index (one past) of the // last slot reserved for digit value v for v = 1 to k - 1 count[v] = count[v] + count[v - 1] // 3. Place elements from the END of A backwards to preserve // stability: equal-digit keys keep their relative input order for j = n downto 1 d_j = digit(A[j], i) output[count[d_j]] = A[j] count[d_j] = count[d_j] - 1 return output ``` The single most important detail is line 3's backward scan in counting sort: it is what makes the per-digit subsort stable. Scanning forward while placing into the highest available slot for each digit value would still sort correctly by digit value, but would reverse the relative order of ties — breaking the entire induction argument that radix sort depends on.

Time complexity. Each pass calls counting sort once. Counting sort on n keys drawn from an alphabet of size k runs in Θ(n + k): Θ(n) to tally digit occurrences and to redistribute elements, plus Θ(k) to build the prefix-sum array over digit values. With d digit positions, the total cost is ``` Θ(d · (n + k)) ``` If d and k are both O(1) — e.g., sorting 64-bit integers with k = 256-byte digits gives d = 8 — the whole algorithm runs in Θ(n), truly linear time. This is not a contradiction of the Ω(n log n) comparison-sort lower bound, because radix sort never compares two keys against each other; it only inspects digit values, which carries more information per operation than a binary comparison.

Space complexity. Each counting-sort pass needs Θ(n + k) auxiliary space for the output array and the count array; this space is reused across passes, so total auxiliary space is Θ(n + k), not Θ(d(n+k)).

Correctness — proof by induction on digit position. Claim: After the pass processing digit position i (having already processed positions 0 through i−1), the array is sorted with respect to the (i+1)-digit suffix consisting of digit positions 0 through i, i.e., for any two elements x, y, if x's digits 0..i (read as a number) are less than y's digits 0..i, then x precedes y in the array; if they are equal, x precedes y iff x preceded y in the original input array (or, inductively, in the array before this pass, which by the inductive hypothesis reflects original order on ties). Base case (i = 0): after one counting-sort pass on digit 0, the array is sorted by digit 0 alone, and counting sort's stability preserves original relative order among elements with equal digit-0 values. This matches the claim for i = 0. Inductive step: assume the claim holds after processing digit i−1, so the array is sorted on the i-digit suffix (positions 0..i−1), ties broken by original order. Now run counting sort on digit i. Two elements x, y are compared only by their digit-i value:

• If digit_i(x) < digit_i(y), the numeric value of x's (i+1)-digit suffix is smaller regardless of lower digits, so x correctly precedes y. Counting sort places them in this order because it sorts by digit i directly.
• If digit_i(x) = digit_i(y), stability guarantees the relative order from before this pass is preserved. By the inductive hypothesis, that prior order already reflects the correct ordering on the lower i digits, ties broken by original input order. So the array remains correctly ordered on the full (i+1)-digit suffix.

Both cases match the definition of "sorted by the (i+1)-digit suffix, ties broken by original order," completing the induction. Taking i = d−1 (all digit positions processed) shows the final array is sorted by the full d-digit key. ∎ The proof pinpoints exactly why stability is not optional: the "ties preserved from before" step in the inductive argument is a direct citation of the stable-subsort property. Remove stability and the induction collapses immediately at i = 1.

Tradeoffs. Radix sort is not a free lunch:

• It requires digits to be extractable in O(1) time (masking/shifting for integers, indexing for fixed-width strings); it is awkward for keys without a fixed decomposable structure, and for keys compared by an arbitrary user-supplied comparator it does not apply at all.
• Θ(d(n+k)) beats Θ(n log n) only when d(n+k) = o(n log n) — for very large k (e.g., sorting arbitrary 64-bit doubles digit-by-digit with k huge and naive digit choice) it can lose to a good comparison sort or to hybrid approaches.
• It is not in-place: each pass allocates Θ(n + k) auxiliary space, unlike in-place comparison sorts such as Quicksort or Heapsort.
• Choosing the digit size (radix) trades off d against k: fewer, larger digits (bigger k) means fewer passes but a bigger count array and worse cache behavior for large k; more, smaller digits means more passes but tiny k. Practical implementations tune the digit width (commonly 8 or 16 bits) to balance this.

Sort the keys 329, 457, 657, 839, 436, 720, 355 (d = 3 decimal digits, k = 10) using LSD radix sort. Below, each row shows the array state and the stable ordering rationale for that pass.

Trace the tricky tie at digit 1 carefully: before this pass the array was 720, 355, 436, 457, 657, 329, 839. Extracting tens digits gives 2, 5, 3, 5, 5, 2, 3. Counting sort tallies: digit 2 appears twice (720, 329), digit 3 appears twice (436, 839), digit 5 appears three times (355, 457, 657). Because the backward scan preserves relative order within each digit bucket, the two elements with tens-digit 5 — 355, 457, 657 — keep exactly the order 355, 457, 657 they had entering this pass, which is precisely why they emerge in that order and, one pass later, fall into their correct final positions (355, 457, 657 already ascending). Had the subsort not been stable, this group could have been scrambled, and no later pass could repair the damage since digit 2 (hundreds) cannot distinguish among numbers that already share the same hundreds digit.

Radix sort's lineage predates electronic computers entirely: it was mechanized in punched-card tabulating machines used for the U.S. census and, later, for Hollerith-style business data processing, where operators physically sorted decks of cards column by column. The insight that sorting by columns (digits) from least significant to most significant yields a fully sorted deck — using the mechanical "stability" of card sorters that never reordered ties within a pass — is the direct ancestor of the LSD algorithm taught today.

Database engines and columnar analytics systems use radix sort (and radix-based hash partitioning) to sort or bucket fixed-width integer and date keys at scale, because Θ(n) behavior on huge tables beats Θ(n log n) comparison sorting when key widths are small and fixed. GPU and parallel sorting libraries favor radix sort because each pass parallelizes cleanly into independent local counting phases followed by a global prefix sum — a pattern well suited to SIMD and multi-core hardware. Suffix array construction algorithms, used in text indexing, bioinformatics genome alignment, and compression, use radix-sort-based ranking of character tuples as an inner loop repeated over increasing prefix lengths. Network routers and switches sort or classify packets by fixed-width fields (IP addresses, port numbers) using radix/trie-based structures descended from the same digit-decomposition idea. Even outside sorting per se, the counting-sort subroutine that powers each radix pass is a building block in bucket-based histogramming, key redistribution in distributed systems, and stable partitioning steps inside more complex algorithms like some variants of Quicksort with three-way partitioning.

Ask the tutor: Can you show me how to adapt LSD radix sort to sort variable-length strings correctly?