Radix Sort sorts numbers by handling their digits one position at a time, from least significant (LSD) to most significant. Each pass re-sorts the whole array by that digit using a stable sub-sort (Counting Sort).

Because every pass is stable, the cumulative effect is a fully sorted array — even though no single pass looks at the “whole” number. For fixed-length keys (integers, strings, IP addresses), this runs in O(d·(n+k)) — linear for all practical purposes.

How It Works

1. Find the maximum value to determine the number of digit passes d.
2. For each digit position (1s, 10s, 100s, …):
   • Perform a stable Counting Sort keyed on that digit.
3. After all d passes, the array is fully sorted.
4. If the input has negatives, first shift all values up by min, then unshift at the end.

Key Insight

The magic is the combination of LSD order and stability. On the 1s pass, numbers group by their units digit. On the 10s pass, numbers regroup by their tens digit — and because that pass is stable, numbers sharing a tens digit keep the order established by their units digit.

Induction on digit positions shows the array is fully sorted after the most significant pass. Radix Sort is also how Hollerith’s punched-card sorter processed data a century before modern computers.

Worked Example

Sort [170, 45, 75, 90, 802, 24, 2, 66] (3 passes, base 10):

• 1s pass (stable): [170, 90, 802, 2, 24, 45, 75, 66] — grouped by units digit 0,0,2,2,4,5,5,6.
• 10s pass: [802, 2, 24, 45, 66, 170, 75, 90] — now grouped by tens digit.
• 100s pass: [2, 24, 45, 66, 75, 90, 170, 802] — grouped by hundreds digit.

Result: [2, 24, 45, 66, 75, 90, 170, 802]. In the visualizer, each digit pass colors the digit currently being compared — notice how within a group, the previous pass’s order is preserved.

Edge Cases & Pitfalls

• Negative values — LSD radix breaks on the sign bit. The standard fix: shift values by min before sorting, unshift after (as the pseudocode does).
• Wide digit range — if k per digit is large or d is huge, cost grows. Radix Sort degrades for numbers with very different lengths.
• Stability is mandatory — LSD passes only work because each is stable. Use Counting Sort, not an unstable digit sort.
• Strings — radix works on fixed-length strings too (character = digit); variable-length strings need padding or an MSD variant.

Comparison With Other Sorts

Applications

• Sorting large collections of integers, strings, or fixed-width keys
• Network addresses and IDs (fixed-digit keys)
• The classic Hollerith punched-card sorter — the first industrial data processing

Practice Trajectory

1. Hand-run the three digit passes on [29, 43, 198, 109, 230, 8] and show the array after each pass.
2. Explain why an unstable digit sort would break LSD radix sort.
3. Trace the negative-shift trick on [−5, 3, −1] and back.
4. Argue why 2-digit numbers need exactly 2 passes.
5. Implement radix sort using the Counting Sort routine you built earlier.