Radix Sort

Sorts by one digit at a time using stable buckets — ones, then tens, then hundreds. Each pass preserves earlier ordering, so d passes fully sort d-digit numbers.

Category

Sorting

Time complexity

O(d·n)

Space complexity

O(n)

Pseudocode

for digit in ones, tens, hundreds
  distribute into 10 buckets
  collect buckets in order
done

Reference implementation

for d in (1, 10, 100):
    buckets = [[] for _ in range(10)]
    for v in a:
        buckets[v // d % 10].append(v)
    a = [v for b in buckets for v in b]

Open the interactive Radix Sort visualisation →