Radix Sort in Python: Sorting Digit by Digit, Faster Than O(n log n)

Every sorting algorithm you have met so far asks one question over and over: is this value bigger than that one? That question is what caps them. There are n! possible orderings of n items, and each yes-or-no comparison can at best halve the candidates that remain, so no algorithm built purely from comparisons can finish in fewer than log2(n!) of them — about n log2 n. Merge sort and heap sort hit that bound. Nothing beats it.

Radix sort never asks the question. It reads the digits of the keys and files them, one digit position per pass. Give it a million 32-bit integers and it sorts them in four passes, taking the same time whether they arrive random, reversed or already sorted.

That is not a violated theorem. The lower bound binds algorithms whose only tool is comparison, and radix sort demands more than a comparison function: the keys have to be made of digits it can index by. Fixed-width integers and fixed-length strings qualify; arbitrary objects with a custom ordering do not. The honest catch is that even where it applies, a hand-written radix sort loses to sorted() in Python at every practical size. The win is real, but it belongs to compiled code moving cheap data.

The idea

Take a list of numbers written with the same number of digits. Sort them by their last digit. Then sort that result by the second-to-last digit, then the third-to-last, and so on up to the first. After one pass per digit position the list is fully sorted.

That is the whole algorithm — LSD radix sort, for least significant digit. The number of passes is d, the digit count of the largest key. The base you write the numbers in is k: a decimal digit means k is 10, a byte means k is 256.

Two things about it look wrong on first reading, and both need answering before the code makes sense.

The per-digit sort must be stable

A sort is stable if items that compare equal come out in the order they went in. For radix sort that is not a nicety, it is the load-bearing wall. Follow the argument below, because it is the entire correctness proof. Claim: after the pass on digit position i, the list is sorted by its last i digits.

Before any pass that is true for free — every list is sorted by zero digits. Now assume it holds after pass i and run pass i + 1. The pass groups the values by digit i + 1, in increasing order of that digit. Inside each group, a stable sort leaves the values in the order they already had, which by assumption is their last-i-digits order. So each group is ordered by digit i + 1 first and by the last i digits second, which is exactly the ordering by the last i + 1 digits.

Run the induction up to i = d and the list is sorted by all d digits. Take stability away and it collapses at the first step: pass i + 1 would be free to shuffle values inside a group, discarding everything the previous i passes established.

The passes must run least significant first

A stable sort makes the digit it sorts on the primary key and whatever order was already there the tie-break. So the last pass decides the ordering that matters most, which means the last pass must be the most significant digit. Counting down instead gives the opposite: the final pass would be on the units digit and the list would come out sorted by last digit only. There is a demonstration of exactly that failure further down.

Watching it work

Sort [170, 45, 75, 90, 802, 24, 2, 66]. The largest value is 802, which has three digits in base 10, so this takes three passes.

Pass 1 — the units digit. Drop each value into the bucket named by its last digit, keeping the input order inside each bucket.

Read the buckets back in order 0, 1, 2, up to 9 and you get [170, 90, 802, 2, 24, 45, 75, 66]. The units digits of that list read 0, 0, 2, 2, 4, 5, 5, 6 — non-decreasing, as promised.

Pass 2 — the tens digit. Bucket that list by its tens digit: 802 and 2 both go to bucket 0, 24 to bucket 2, 45 to bucket 4, 66 to bucket 6, 170 and 75 to bucket 7, 90 to bucket 9. Reading back gives [802, 2, 24, 45, 66, 170, 75, 90].

Look at bucket 7. It holds 170 then 75, and this pass did not decide that — both have a tens digit of 7, so it had no opinion. Pass 1 decided it, putting 170 (units digit 0) ahead of 75 (units digit 5). Their last two digits now read 70 and 75. Stability is doing visible work.

Pass 3 — the hundreds digit. Bucket 0 collects everything under 100 — 2, 24, 45, 66, 75, 90, in the order pass 2 left them. Bucket 1 gets 170, bucket 8 gets 802. Read back: [2, 24, 45, 66, 75, 90, 170, 802]. Done.

Pass 3 is where stability pays for itself most obviously. Six of the eight values share a hundreds digit of 0, so that pass has no opinion about their relative order and must leave them exactly as it found them. If it did not, the result would be garbage even though every individual pass was "correct":

The code

Start with the version that reads like the description: ten literal buckets, one per digit.

def radix_sort_buckets(numbers: list[int], trace: bool = False) -> list[int]:
    """Sort non-negative integers by bucketing them on one digit at a time.

    One pass per digit position, least significant first. Appending to a
    bucket preserves arrival order, and that stability is what makes the
    earlier passes survive the later ones.
    """
    values = list(numbers)
    if not values:
        return values

    largest = max(values)
    place = 1
    while largest // place > 0:
        buckets: list[list[int]] = [[] for _ in range(10)]
        for value in values:
            buckets[(value // place) % 10].append(value)
        # Reading bucket 0 then 1 then 2 ... is the entire "sort" step.
        values = [value for bucket in buckets for value in bucket]
        if trace:
            print(f"place {place:>3}: {values}")
        place *= 10

    return values


print(radix_sort_buckets([170, 45, 75, 90, 802, 24, 2, 66]))
print(radix_sort_buckets([]))
print(radix_sort_buckets([4]))
print(radix_sort_buckets([0, 0, 7, 0]))
radix_sort_buckets([170, 45, 75, 90, 802, 24, 2, 66], trace=True)

[2, 24, 45, 66, 75, 90, 170, 802]
[]
[4]
[0, 0, 0, 7]
place   1: [170, 90, 802, 2, 24, 45, 75, 66]
place  10: [802, 2, 24, 45, 66, 170, 75, 90]
place 100: [2, 24, 45, 66, 75, 90, 170, 802]

The three traced lines are the walkthrough, printed by the real thing. (value // place) % 10 is the digit extractor: dividing by place shifts the digit you want down into the units position, and % 10 discards everything above it. The condition largest // place > 0 stops as soon as place passes the top digit of the largest value, so the data decides the pass count.

That version allocates ten lists per pass and grows them one append at a time. The real implementation replaces the buckets with a counting sort: count how many values carry each digit, turn the counts into starting offsets, then copy each value straight into its final slot. Same result, one output array, no per-bucket allocation.

def counting_sort_by_digit(values: list[int], place: int, base: int) -> list[int]:
    """Stably sort values by the single digit that `place` selects.

    Three linear scans: count how many values carry each digit, turn those
    counts into the output index each digit's run begins at, then copy every
    value into its slot in input order.
    """
    counts = [0] * base
    for value in values:
        counts[(value // place) % base] += 1

    # counts[digit] becomes the index the first value with that digit takes,
    # because every value with a smaller digit sits in front of it.
    start = 0
    for digit in range(base):
        counts[digit], start = start, start + counts[digit]

    output = [0] * len(values)
    for value in values:
        digit = (value // place) % base
        output[counts[digit]] = value
        counts[digit] += 1  # the next value with this digit lands one slot along

    return output


def radix_sort(numbers: list[int], base: int = 256) -> list[int]:
    """LSD radix sort for non-negative integers.

    Runs one stable counting sort per digit, least significant first. The
    number of digits d is fixed by the largest value and the base, so the
    whole sort costs O(d * (n + base)).
    """
    values = list(numbers)
    if len(values) < 2:
        return values
    if min(values) < 0:
        raise ValueError("radix_sort handles non-negative integers only")

    largest = max(values)
    place = 1
    while largest // place > 0:
        values = counting_sort_by_digit(values, place, base)
        place *= base

    return values


print(counting_sort_by_digit([170, 45, 75, 90, 802, 24, 2, 66], place=1, base=10))
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66], base=10))
print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))

import random

random.seed(11)
sample = [random.randrange(10_000_000) for _ in range(5_000)]
print(radix_sort(sample) == sorted(sample))
print(radix_sort(sample, base=10) == sorted(sample))

[170, 90, 802, 2, 24, 45, 75, 66]
[2, 24, 45, 66, 75, 90, 170, 802]
[2, 24, 45, 66, 75, 90, 170, 802]
True
True

The single call to counting_sort_by_digit reproduces the units pass exactly. Five thousand random seven-digit values agree with sorted() in base 10 and in base 256 — three passes in one case, four in the other, same answer.

How the code maps to the idea

The count-then-offset trick is the counting sort. Two values end in 0, two in 2, one in 4, two in 5, one in 6. Turn those counts into running totals and you know where every digit's run starts before you move a single value.

Value 170 has digit 0, so it takes index 0 and the offset for digit 0 becomes 1. Value 45 has digit 5 and takes index 5. Value 75 also has digit 5, and because the offset moved on it takes index 6 — behind 45, where it started. The forward scan plus the advancing offset is the stability. Textbooks often write this mirrored, storing the end of each run and walking the input backwards; that is equally stable.

The base parameter trades passes against memory. A larger base means fewer digits and fewer passes, but a bigger counts array to zero and scan. Base 256 is the usual choice for machine integers: a digit is then exactly one byte, and the extractor becomes a shift and a mask.

The negative-number guard exists because Python's floor division makes that failure silent rather than loud. -3 % 10 is 7, so −3 files itself into bucket 7 and the sort returns a wrong answer with no error. If you need negatives, shift the whole list up so the smallest value is zero — adding a constant to every value cannot change their relative order:

def radix_sort_signed(numbers: list[int], base: int = 256) -> list[int]:
    """Radix sort that also accepts negative integers.

    Adding the same constant to every value cannot change their order, so
    lift the list until the smallest value is zero, sort, then lower it back.
    """
    if not numbers:
        return []

    smallest = min(numbers)
    if smallest >= 0:
        return radix_sort(numbers, base)

    lifted = radix_sort([value - smallest for value in numbers], base)
    return [value + smallest for value in lifted]


def radix_sort_fixed_strings(words: list[str], width: int) -> list[str]:
    """LSD radix sort for equal-length ASCII strings, one character per pass."""
    values = list(words)
    for position in reversed(range(width)):
        buckets: list[list[str]] = [[] for _ in range(128)]
        for word in values:
            buckets[ord(word[position])].append(word)
        values = [word for bucket in buckets for word in bucket]
    return values


print(radix_sort_signed([3, -7, 0, -102, 45, -7]))
print(radix_sort_fixed_strings(["dog", "cat", "cow", "bat", "ant", "owl"], width=3))

[-102, -7, -7, 0, 3, 45]
['ant', 'bat', 'cat', 'cow', 'dog', 'owl']

Strings are the same algorithm with a different digit extractor. A character is a digit in base 128 for ASCII, or base 256 over raw bytes. The one requirement is that all keys share a length, because each pass handles the same position in every key at once. Variable-length keys need right-padding, or the MSD variant described below.

Edge cases fall out of the arithmetic. Empty and single-item lists return immediately. A list of nothing but zeros has largest equal to 0, so largest // 1 is 0 and no pass ever runs — correct, because a list of equal values is already sorted.

Complexity

Count one pass first. It does four things: read n values and bump a counter for each, zero a k-entry table, prefix-sum that table, then read n values again and write each into the output. That is roughly 3n element touches plus 2k table touches, so one pass is O(n + k).

There are d passes, one per digit position, so the total is O(d * (n + k)). There is no best or worst case: nothing the algorithm does depends on the values' relative order, so sorted, reversed and random input all cost the same.

Space is O(n + k) — one output array of n slots, reused across passes, plus one count array of k entries.

Now the question that decides whether that bound is any good: what is d? It is the number of digits the largest key needs in base k, which is floor(log_k(largest)) + 1, and it has nothing to do with n. For machine integers it is a constant fixed before you see the data:

With d and k both constants, O(d * (n + k)) collapses to O(n). That is the headline claim, and it is true — for fixed-width keys.

It stops being true if you let the key width grow with the data. If all n keys are distinct non-negative integers then the largest is at least n − 1, so d is at least log_k(n) and the cost is at least n log_k(n). Radix sort has not repealed the comparison bound; it has changed the base of the logarithm from 2 to k and moved the work from branchy comparisons to flat array indexing. Both are worth a lot in practice. Neither is magic.

Put numbers on it. Element touches for a 32-bit radix sort in base 256 — one read and one write per value per pass — against log2(n!), the fewest comparisons any comparison sort can get away with:

import math


def radix_touches(n: int, key_bits: int, radix_bits: int) -> int:
    """Reads plus writes for an LSD radix sort: two per item per pass."""
    passes = math.ceil(key_bits / radix_bits)
    return passes * 2 * n


def comparison_floor(n: int) -> int:
    """log2(n!) — the fewest comparisons any comparison sort can get away with."""
    return math.ceil(math.lgamma(n + 1) / math.log(2))


for size in (1_000, 100_000, 10_000_000):
    print(
        f"n = {size:>10,}   radix touches: {radix_touches(size, 32, 8):>12,}"
        f"   comparisons needed: {comparison_floor(size):>12,}"
    )

n =      1,000   radix touches:        8,000   comparisons needed:        8,530
n =    100,000   radix touches:      800,000   comparisons needed:    1,516,705
n = 10,000,000   radix touches:   80,000,000   comparisons needed:  218,108,030

At a thousand items the two columns are level. At ten million, radix sort does under one touch for every two comparisons the alternative needs, and the gap keeps widening because one column grows linearly and the other does not.

Those are operation counts, not seconds, and the difference is where the honest caveats live. The write in the placement scan jumps to a different offset for every digit, so once the output array outgrows the L2 cache almost every element costs a scattered write, and a cache miss is worth more than a hundred arithmetic operations. Fast implementations fight that with small radixes and software write-combining buffers. In CPython, meanwhile, each of those touches is interpreted bytecode on a boxed integer while sorted() compares inside C. Time the two and sorted() wins at every size you are likely to hit.

When to use it, and when not to

Use it when all four of these hold. The keys are fixed-width integers, fixed-length strings, or anything you can turn into a fixed-length byte string that compares correctly. n is large — hundreds of thousands at least, or the constant factor eats the win. The per-element cost is low, meaning C, Rust, a GPU kernel or a NumPy array. And you can afford O(n) extra memory for the output buffer.

Reach for something else otherwise. In Python that means sorted(items) or items.sort(), which run Timsort in C: O(n log n) worst case, stable, adaptive to runs the data already contains, one function call. If the data is already in a NumPy array of an integer dtype, numpy.sort(array, kind="stable") is documented to dispatch to a radix sort, so you get this algorithm without writing it.

If your keys sit in a small known range — ages, scores out of 100, bytes — skip radix sort and use plain counting sort. It is one pass of the same machinery, O(n + k), with no digit loop at all. Radix sort exists for the case where k would be far too large for a single counting pass, and splits the key into digits to keep k small.

MSD radix sort, briefly

The other direction sorts on the most significant digit first, splits the input into k buckets by that digit, and then recursively sorts each bucket independently. Because buckets never mix again after a split, correctness no longer depends on a stable per-digit sort — though each bucket's sort must still be stable if you want the whole thing stable.

MSD earns its complications on strings. It stops as soon as a bucket holds one key and never reads the rest of that key: a million 40-character identifiers that all become distinct within three characters cost MSD three passes and LSD forty. It handles variable-length keys naturally, and it walks exactly the structure a trie stores. The costs are recursion, per-bucket bookkeeping and poor cache behaviour across the many tiny buckets near the leaves, so real implementations drop to insertion sort below a few dozen items. American flag sort is the well-known in-place MSD variant.

Where it shows up in the real world

Punched-card sorting machines. This is where the algorithm comes from, and the mechanism is the buckets diagram above made of metal. An IBM Type 80 sorter and its descendants had a row of pockets, one per digit, and read one card column per run. Operators fed the deck through starting at the rightmost column, restacked the pockets in order, and repeated for the next column leftwards — LSD radix sort performed by a machine that could not compare two cards to save its life. Harold Seward wrote both counting sort and radix sort down as computer algorithms in his 1954 MIT master's thesis.

NumPy. numpy.sort(array, kind="stable") maps to a radix sort for integer dtypes rather than to a merge sort — the most likely place a Python programmer runs this algorithm without noticing.

GPU sorting. cub::DeviceRadixSort in NVIDIA's CUB library is the standard high-performance GPU sort, and thrust::sort dispatches to it for primitive types. Radix sort suits GPUs unusually well: each pass is a histogram followed by a scatter, both embarrassingly parallel, whereas comparison sorts need threads to co-ordinate at every merge.

Database engines. DuckDB's sort operator normalises each sort key into a binary-comparable byte string and radix-sorts those fixed-width keys, which is how it orders by several columns of mixed types with one pass structure.

Suffix array construction. The DC3/skew and SA-IS algorithms both radix-sort tuples of characters as an inner step. Suffix arrays underpin the Burrows-Wheeler transform used by bzip2, and the read aligners used in bioinformatics.

Common mistakes

Using an unstable sort for a pass. Nobody picks a quicksort on purpose here. What people actually do is prepend to buckets instead of appending, collect a bucket into a set, or sort each bucket's contents "to be safe". All three scramble the order inside a group and wipe out the earlier passes.

Running the passes most significant first. The two directions look symmetric, so this bug survives review. They are not symmetric, and the result is sorted by the last digit:

def most_significant_first(numbers: list[int]) -> list[int]:
    """The right passes in the wrong order: most significant digit first."""
    values = list(numbers)
    place = 1
    while max(values) // place > 0:
        place *= 10

    place //= 10
    while place > 0:
        buckets: list[list[int]] = [[] for _ in range(10)]
        for value in values:
            buckets[(value // place) % 10].append(value)
        values = [value for bucket in buckets for value in bucket]
        place //= 10

    return values


print(most_significant_first([170, 45, 75, 90, 802, 24, 2, 66]))
print(radix_sort_buckets([5, -3, 8]))

try:
    radix_sort([5, -3, 8])
except ValueError as error:
    print(f"radix_sort refused: {error}")

[170, 90, 2, 802, 24, 45, 75, 66]
[5, -3, 8]
radix_sort refused: radix_sort handles non-negative integers only

The units digits of that first line read 0, 0, 2, 2, 4, 5, 5, 6. Sorted, by the wrong key. Going top-down only works if you recurse into each bucket separately, which is MSD radix sort, not a reordering of LSD.

Feeding it negatives. The second line above shows the silent failure: [5, -3, 8] comes back untouched and unsorted, because Python's % maps −3 to bucket 7. Guard the input or shift it.

Getting the loop bound wrong. while place < largest skips the top digit whenever the largest value is an exact power of the base — 100 gets two passes instead of three. while largest // place > 0 is the version that always terminates on the right pass.

Choosing a base far larger than n. Base 65536 looks efficient because it cuts 32-bit keys to two passes, but each pass zeroes and scans a 65,536-entry table. Sort 1,000 items that way and you spend over a hundred table operations per item. Keep k in the same neighbourhood as n.

Assuming O(n) means fastest. It means the growth is linear, not that the constant is small. A cache-missing scatter per element is expensive, and below roughly a hundred thousand items a good O(n log n) sort usually finishes first.

Practice

1. Change radix_sort_buckets to print how many values land in each bucket on every pass, and check the counts always sum to n.
2. Sort a list of (name, score) pairs by score with a radix sort, then use two pairs with equal scores to show the input order survives.
3. Handle negative integers without the shift trick: split the list, radix-sort the absolute values of the negatives, reverse that half, and join.
4. Write MSD radix sort for variable-length lowercase words, recursing into each bucket and stopping when a bucket holds one word or the position runs past the end of a key.
5. For one million 32-bit keys, compute d * (n + k) for bases 10, 256, 1024 and 65536, and find which base minimises it.

Summary

Radix sort sorts without ever comparing two keys, which is how it escapes the n log n bound that binds every comparison sort. The cost is that it only works on keys made of indexable digits, and the O(n) headline holds only while the key width stays fixed as n grows. Learn it for the stability argument — that induction over digit positions is one of the most elegant correctness proofs in the whole subject — and use sorted() unless you are moving millions of fixed-width keys in compiled code.

Keep reading

• Counting Sort in Python — the single stable pass that radix sort calls d times, and the right tool when the key range is already small.
• Merge Sort in Python — where the n log n bound comes from, built up from one merge.
• Big O Notation — the full counting method used throughout this post.