Radix Sort

Understand the idea

This simple non-negative base-ten version uses buckets and concatenates them in digit order. It is an educational least-significant-digit approach, not a universal sorter for negative integers or arbitrary text. Work depends on the number of digit passes as well as input length. Keep duplicate values and zero in your tests.

Where to try it

Open this example with Try in playground. The code loads as editable text and does not run until you select Run. The first run downloads Python. Each run starts fresh; temporary files created by a script are not files on your PC.

A worked example

def radix_sort(values):
    result = list(values)
    if not result:
        return result
    if min(result) < 0:
        raise ValueError("Non-negative integers required")
    place = 1
    while max(result) // place > 0:
        buckets = [[] for _ in range(10)]
        for value in result:
            buckets[(value // place) % 10].append(value)
        result = [value for bucket in buckets for value in bucket]
        place *= 10
    return result

print(radix_sort([42, 7, 105, 7, 0]))

Read the result

The result is [0, 7, 7, 42, 105]. Stable buckets let later digit passes preserve the ordering established earlier.

Try one change

Trace the units and tens passes separately, including the zero and repeated 7.