DSA Radix Sort

Radix sort is a sorting method that sorts numbers one digit at a time. Each digit pass uses a stable counting sort, so earlier digit work is never undone.

Reading one digit

The digit at a place comes from dividing and taking the remainder. The ones place uses a divisor of 1.

nums = [170, 45, 802, 2]
for n in nums:
    print(n, "ones digit:", (n // 1) % 10, "tens digit:", (n // 10) % 10)

One stable counting pass

A counting pass groups values by one digit. Values are placed in their old order inside each group.

def counting_pass(nums, place):
    counts = [0] * 10
    for n in nums:
        counts[(n // place) % 10] += 1
    starts = [0] * 10
    total = 0
    for d in range(10):
        starts[d] = total
        total += counts[d]
    result = [0] * len(nums)
    for n in nums:
        d = (n // place) % 10
        result[starts[d]] = n
        starts[d] += 1
    return result

nums = [21, 13, 31, 23]
print("before:", nums)
print("after ones pass:", counting_pass(nums, 1))

Counting the passes

The largest value sets the pass count. A three-digit maximum means three passes.

nums = [45, 802, 24, 66]
biggest = max(nums)
passes = 0
place = 1
while place <= biggest:
    passes += 1
    place *= 10
print("largest:", biggest)
print("passes needed:", passes)

Example

def counting_pass(nums, place):
    counts = [0] * 10
    for n in nums:
        counts[(n // place) % 10] += 1
    starts = [0] * 10
    total = 0
    for d in range(10):
        starts[d] = total
        total += counts[d]
    result = [0] * len(nums)
    for n in nums:
        d = (n // place) % 10
        result[starts[d]] = n
        starts[d] += 1
    return result

nums = [170, 45, 75, 90, 802, 24, 2, 66]
print("start:", nums)
place = 1
step = 1
while place <= max(nums):
    nums = counting_pass(nums, place)
    print("after pass", step, ":", nums)
    place *= 10
    step += 1
print("sorted:", nums)
print("matches built-in sort:", nums == sorted(nums))

Key points

Radix sort sorts digit by digit, from the last digit to the first.
A stable pass keeps equal-digit values in their previous order.
Stability means values that tie on one digit keep the order the last pass gave them.
The number of passes equals the digit count of the largest value.
Radix sort spends its work on counting, not on comparisons.

In this example, eight non-negative numbers are sorted by three digit passes. The ones pass groups the numbers by their last digit. The tens pass then orders them by the middle digit without breaking the ones order. The hundreds pass finishes the job. The last line checks the result against the built-in sort and prints True.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

def counting_pass(nums, place):
    counts = [0] * 10
    for n in nums:
        counts[(n // place) % 10] += 1
    starts = [0] * 10
    total = 0
    for d in range(10):
        starts[d] = total
        total += counts[d]
    result = [0] * len(nums)
    for n in nums:
        d = (n // place) % 10
        result[starts[d]] = n
        starts[d] += 1
    return result

nums = [170, 45, 75, 90, 802, 24, 2, 66]
print("start:", nums)
place = 1
step = 1
while place <= max(nums):
    nums = counting_pass(nums, place)
    print("after pass", step, ":", nums)
    place *= 10
    step += 1
print("sorted:", nums)
print("matches built-in sort:", nums == sorted(nums))

Exercise

A list's largest value is 4096. How many digit passes does radix sort run?

Two Three Four Ten