Radix Sort

Radix sort is a non-comparison sorting algorithm that orders integers one digit at a time, from the least significant digit to the most significant, using a stable bucket distribution on every pass. It runs in O(d·n) time for d-digit keys, uses O(n + b) extra space (b is the number of buckets — 10 for decimal digits), and is stable.

Unlike every comparison sort, it never once asks "is a bigger than b?"

Picture a mailroom sorting parcels by a six-digit zip code. Nobody compares two zips end to end. You drop every parcel into one of ten bins by its last digit, stack the bins back into a pile, then do it again by the next digit, and again, until you have run through all six. After the last pass the pile is in full zip order — and the only thing you ever read off a parcel was a single digit at a time. That is radix sort. The clever part is not the bins; it is that each pass leaves the previous pass's work intact.

How Radix Sort Works

Radix sort is a loop wrapped around a smaller sort. The outer loop walks the digit places — ones, tens, hundreds — one pass each, so a list whose largest value has d digits takes exactly d passes. Each pass runs a stable counting sort keyed on the current digit: distribute every number into the bucket named by that digit (0–9), then collect the buckets back into the list in order, 0 through 9.

Two properties make this correct, and both are easy to miss:

• Stability is load-bearing, not a bonus. Within a single pass, many numbers can share the same digit — they all land in one bucket. They must come out in the same order they went in. Because we sort by the least significant digit first and the most significant last, a later pass only re-sorts ties from the digit it cares about; the order among those ties was already fixed by the earlier, less-significant passes. Break stability and the whole scheme collapses.
• A missing higher digit is a zero. An 8 has no tens digit, so on the tens pass its digit is 0 and it routes to bucket 0. That is why short numbers drift to the front exactly when they should.

The per-digit sort shown in the code is the bucket-list form: ten lists, append to distribute, concatenate to collect. The textbook also writes counting sort with a count array and a prefix sum, which avoids the list overhead. The two are equivalent — both stable, both O(n + b) per pass. The list form is shown here because it is the picture on screen: ten visible bins filling and draining.

Radix Sort Step by Step

The default input is [35, 42, 8, 32, 12, 25]. The largest value is 42, which has two digits, so radix sort makes two passes: ones, then tens.

Pass 1 — the ones digit. Read each number's last digit and drop it into that bucket, left to right:

• 35 → bucket 5
• 42 → bucket 2
• 8 → bucket 8
• 32 → bucket 2 (lands behind 42)
• 12 → bucket 2 (lands behind 32)
• 25 → bucket 5 (lands behind 35)

Bucket 2 now holds [42, 32, 12], bucket 5 holds [35, 25], bucket 8 holds [8], and every other bucket is empty. Collect the buckets in order 0→9, taking each bucket front to back: [42, 32, 12, 35, 25, 8]. The list is now sorted by its ones digit — read the last digits left to right and they only ever climb: 2, 2, 2, 5, 5, 8.

Pass 2 — the tens digit. Run the same distribution on the result of pass 1, this time keyed on the tens digit:

• 42 → bucket 4
• 32 → bucket 3
• 12 → bucket 1
• 35 → bucket 3 (lands behind 32)
• 25 → bucket 2
• 8 → bucket 0 (its tens digit is an implicit 0)

Watch bucket 3. It holds [32, 35] — and 32 sits ahead of 35 not because we compared them now, but because pass 1 already put 32 before 35 and the append kept that order. That single beat is the whole idea of radix sort: stability carrying earlier work forward.

Collect 0→9: [8, 12, 25, 32, 35, 42]. Sorted, in two passes, without a single comparison between two values.

Time and Space Complexity

Radix sort has no input-dependent best or worst case the way comparison sorts do — its cost is set entirely by n (how many numbers) and d (how many digits the largest one has). When d is small and fixed, O(d·n) beats the O(n log n) comparison barrier, because that barrier only applies to sorts that learn about order by comparing.

The catch is d. Load the Wide key scenario — [7, 3, 9, 2, 50000] — and one five-digit number drags the whole list through five passes. Four of them do nothing but shuffle the lone big value while the four small numbers pile back into bucket 0. The timeline visibly balloons. That is the honest reading of O(d·n): radix sort is not magic O(n), it is O(n) per digit, and a wide key means many digits.

Edge Cases

• Empty list — the if not arr guard returns it immediately: no max, no passes.
• Single-element list — one pass over a one-digit max; the lone number distributes into its bucket and collects straight back, unchanged.
• Single-digit numbers in a multi-digit list — handled by the implicit-zero rule: on any higher pass their digit is 0, so they sort to the front. The 8 in the default input is exactly this case.
• Duplicate values — preserved and grouped; stability keeps equal keys in their original relative order.
• All numbers share a digit — load the Same tens digit scenario [34, 31, 38, 32, 36, 35]: the tens pass dumps the entire list into one bucket and reorders nothing. The ones pass already did all the real work — a reminder that a pass can be a no-op and the algorithm still pays for it.
• Negative numbers — this LSD-by-decimal-digit version assumes non-negative integers. Negatives need a sign-aware variant (sort magnitudes, then reverse the negative block), which this lesson does not cover.

Common Mistakes

• Sorting most-significant digit first with this scheme. LSD radix sort goes least-significant first on purpose. If you lead with the most significant digit using the same flat bucket-and-collect, later passes scramble the order the first pass established. (There is a separate MSD radix sort, but it must recurse within each bucket rather than re-flatten — a different algorithm.)
• Using an unstable inner sort. Swap the stable bucket distribution for anything that can reorder ties and the whole method breaks. On the tens pass in the walkthrough, bucket 3 holds [32, 35]. If the inner sort emitted 35 before 32, the final array would be [8, 12, 25, 35, 32, 42] — those two out of order, and nothing later ever re-checks the ones digit to catch it. The result is correct only because the tie kept its [32, 35] order.
• Looping a fixed number of passes instead of deriving it from the max. Hard-coding "three passes" silently truncates any value with more digits and wastes passes on lists of small numbers. The pass count is digits(max(arr)), computed from the data.
• Assuming radix sort is always faster than O(n log n). It is O(d·n). For wide or variable-width keys, d is large and a good comparison sort wins. Radix sort pays off when the keys are short, fixed-width, and bounded — integers, fixed-length strings, dates.