Radix Sort

The Idea

Radix sort is counting sort run once per digit, starting from the least significant one. Each pass drops every number into one of ten buckets and collects them back in bucket order. Because a pass is stable, numbers that tie on the current digit keep the order the previous pass gave them — which is exactly why starting from the right works. Cost is d passes over n numbers, with no comparisons at all.

Real-World Example

Old postal sorting. Letters are thrown into pigeonholes by the last digit of the code, gathered up in order, and thrown again by the next digit. After the final round the stack is in delivery order and nobody read a full address.

The Code

def radix_sort(nums):
    place = 1
    while place <= max(nums):
        buckets = [[] for _ in range(10)]
        for x in nums:
            buckets[(x // place) % 10].append(x)   # ties keep their order
        nums = [x for b in buckets for x in b]     # collect 0..9 in order
        place *= 10
    return nums

print(radix_sort([170, 45, 75, 90, 2, 802]))   # [2, 45, 75, 90, 170, 802]

nums = [53, 12, 21, 45]
buckets = [[] for _ in range(10)]
for x in nums:
  buckets[x % 10].append(x)
print([x for b in buckets for x in b])