Radix Sort: Digit-by-Digit Sorting
What you'll learn: How to sort numbers by processing each digit position separately, from least significant to most significant.
The Core Idea
Imagine sorting a deck of playing cards first by suit, then by rank within each suit. Radix Sort applies this idea to numbers by sorting them digit-by-digit. The clever trick: you sort by the rightmost (least significant) digit first, then move leftward. Since each digit-level sort must be stable (preserving relative order of equal elements), numbers gradually fall into correct order.
For example, sorting [170, 45, 75, 90, 802, 24, 2, 66]:
Pass 1 (ones place): Group by last digit → [170, 90, 802, 2, 24, 45, 75, 66]
Pass 2 (tens place): Group by second digit → [802, 2, 24, 45, 66, 170, 75, 90]
Pass 3 (hundreds place): Group by third digit → [2, 24, 45, 66, 75, 90, 170, 802] ✓
Why Use a Stable Subroutine?
The digit-by-digit approach only works if your sorting subroutine is stable. This is why Counting Sort (which we covered earlier) is the typical choice for each digit pass. Stability ensures that when two numbers have the same digit in the current position, their order from previous passes is preserved.
The Process
- Find the maximum number to determine how many digits to process
- For each digit position (starting from rightmost):
- Use a stable sort (like Counting Sort) on just that digit
- The array becomes progressively more sorted
- After processing all digit positions, the array is fully sorted
Key Takeaway: Radix Sort processes multi-digit numbers by repeatedly applying a stable sorting algorithm to each digit position, building up the final sorted order from least to most significant digit.