Sorting mail by pincode, one digit at a time
Every sort you have learned compares two values directly. Radix sort never compares anything — it buckets by digit, again and again, until the numbers fall into order on their own.
After this lesson
You should be able to
- Sort a list of numbers by hand using radix sort.
- Explain why radix sort processes the least significant digit first.
- Explain why radix sort is not a comparison-based algorithm.
The post office did this before computers did
Old mail-sorting machines separated letters into ten bins by the last digit of the pincode, collected them back in bin order, then repeated using the second-to-last digit, and so on. By the time every digit position had been processed, the whole stack of mail was fully sorted — without ever directly comparing two pincodes to each other.
Every sort you have met so far — bubble, insertion, selection, and the tree sort coming later this unit — decides order by comparing two values and asking which is bigger. Radix sort refuses to play that game at all.
Bucket by digit, least significant first
For each digit position, from the ones place outward, place every number into one of ten buckets (0 through 9) matching that digit, then collect the buckets back into a single list in bucket order. Repeat for the tens place, then the hundreds place, and so on for as many digits as the largest number has.
The order matters precisely: you must start from the ones digit, not the highest digit. Starting from the highest digit first would sort by the most significant place correctly but then scramble that order while sorting by lower digits — starting from the least significant digit and collecting stably, in original order within each bucket, is what makes each pass preserve the good ordering the previous pass already achieved.
Numbers: 170, 45, 75, 90, 802, 24, 2, 66
Pass 1 (ones digit):
0: 170, 90
2: 802, 2
4: 24
5: 45, 75
6: 66
-> collected: 170, 90, 802, 2, 24, 45, 75, 66
Pass 2 (tens digit):
0: 802, 2
2: 24
4: 45
6: 66
7: 170, 75
9: 90
-> collected: 802, 2, 24, 45, 66, 170, 75, 90
Pass 3 (hundreds digit):
0: 2, 24, 45, 66, 75, 90
1: 170
8: 802
-> collected: 2, 24, 45, 66, 75, 90, 170, 802 (sorted!)Why 'no comparisons' is a big deal
There is a proven limit on how fast a comparison-based sort can ever be, no matter how cleverly written — roughly n times the logarithm of n comparisons, at best. Radix sort sidesteps that limit entirely by not comparing at all, instead doing work proportional to the number of digits times the number of values — which can beat the comparison limit when the numbers involved do not have too many digits.
The trade-off: radix sort needs the extra bucket arrays, and it only makes sense for data with a natural fixed-digit representation — integers, fixed-length strings, dates — not for arbitrary comparable objects, which is where the comparison-based sorts this unit also covers remain necessary.
Try it yourself
Sort 329, 457, 657, 839, 436, 720, 355 using radix sort, showing the buckets at each of the three passes.
Need a hint?
Every number here has three digits, so exactly three passes are needed, ones first.
Check the worked solution
After the ones-digit pass: 720, 355, 436, 457, 657, 329, 839. After the tens-digit pass: 720, 329, 436, 839, 355, 457, 657. After the hundreds-digit pass: 329, 355, 436, 457, 657, 720, 839 — sorted. Each pass only reorders within what the previous pass already got right, which is the stability property doing its job.
Quick check
Why must radix sort process the ones digit first, rather than the highest-value digit first?
Why this lesson exists
Syllabus mapping
Radix Sort
Maps to course outcomes CO1, CO3.