Non-comparison sorts: counting, radix, bucket

What this chapter covers

There's a theorem that says no sort can beat O(n log n). It's true — for sorts that work by comparing elements. This chapter is about the loophole: if you don't compare elements but instead use their values as array indices, you can sort in O(n). Counting sort tallies how many of each value; radix sort does it digit by digit; bucket sort scatters into ranges. All three run in linear time on the right data, and counting sort in this chapter's face-off actually beats Python's C-optimized sorted — one of the rare times hand-written code out-scales the library. The price is generality: these work only on integers with a bounded range.

A bit of history

Radix sort is older than the computer. In 1890 Herman Hollerith built electric tabulating machines to process the US census, and his card sorters worked by radix: they'd sort a stack of punched cards by one column, then the next, physically bucketing the cards digit by digit — exactly the least-significant-digit radix sort in this chapter, done with metal and cardboard. That machinery founded the company that became IBM. Counting sort was described by Harold Seward in 1954, along with the radix sort built on top of it, in one of the first systematic treatments of sorting on a stored-program computer. So these algorithms bracket the birth of computing: radix sort ran on 1890s tabulators, and counting sort was among the first things written for the 1950s machines. They predate quicksort, and they've never been improved on for what they do — sort bounded integers in linear time.

The intuition

The comparison sorts all ask the same question over and over: is this element bigger than that one? Counting sort asks a different question — how many elements equal each value? If your values are integers from 0 to k, make an array of k+1 counters, sweep the input incrementing the counter for each value you see, and you now know exactly how many of each there are. Read the counters back out in order — count[0] zeros, then count[1] ones, and so on — and that's the sorted output. Not one comparison happened; you sorted by tallying.

Counting sort needs a counter per possible value, so it's only practical when the range k is small. Radix sort removes that limit: sort by the last digit (a counting sort over just ten buckets), then the next-to-last, up to the most significant, and — because each pass is stable — the array comes out fully sorted after d passes. Bucket sort takes yet another angle: split the value range into buckets, drop each element into its bucket, sort the small buckets, and concatenate. When the data is spread evenly, every bucket is tiny and the whole thing is linear. Three ways to sort without comparing, each trading generality for speed.

Complexity: how it scales

Counting sort is $O(n + k)$: one pass over the n elements to tally, one pass over the k counters to emit. When k is comparable to n (or smaller), that's $O(n)$ — linear. Radix sort is $O(d \cdot (n + b))$ for d digits in base b; with b fixed at 10 and d small (a 32-bit integer is 10 decimal digits), it's linear in n. Bucket sort is $O(n)$ expected when the data is uniformly distributed across its buckets, degrading toward the cost of its inner sort when it isn't. The chart sorts bounded integers and shows counting sort undercutting even Timsort:

At 160000 integers in the range 0–1000, counting sort took about 3.9 ms against Timsort's 12.8 ms — 3.3 times faster than the C library sort, from pure Python, because it does a single linear tally where Timsort does n log n comparisons. That's the payoff of using the right specialized tool.

What it's good at, what it isn't

These sorts are the right choice when your keys are bounded integers — and that's more common than it sounds. Ages, days of the year, byte values, small IDs, exam scores, priorities: all bounded integers, all sortable in linear time. Counting sort is also the stable building block inside radix sort, and it's the fastest possible sort when k is small. When the data fits their assumptions, nothing beats them.

But those assumptions are strict, and violating them is a trap. Counting sort's cost is $O(n + k)$, so a wide range is fatal — sorting a handful of values that happen to range up to a billion would allocate a billion counters. They only sort integers (or keys you can map to integers), so no arbitrary objects, no custom comparators, no floats-in-general. And bucket sort's linear time assumes an even distribution; feed it clustered data and it degrades. For general-purpose sorting of arbitrary comparable things, a comparison sort is still the answer. These are specialists.

The data, or the inputs

The face-off sorts integers with a deliberately small key range (0–1000) so counting sort's O(n + k) is genuinely O(n), plus a wider range (up to a million) for radix sort. The animation counts twelve small integers, so you can watch the tally histogram build one element at a time and see that no two elements are ever compared.

Build it, one function at a time

Counting sort is the foundation — tally by value, then read the tallies back in order:

def counting_sort(a, probe=None):
    """O(n + k) for integers in [0, k): sort by COUNTING, not comparing. Tally how
    many of each value there are, then read the tallies back out in order. There is
    not a single comparison between elements — which is exactly how it dodges the
    O(n log n) comparison bound."""
    if not a:
        return []
    k = max(a) + 1
    count = [0] * k
    for x in a:
        count[x] += 1                    # the whole sort is this tally
        if probe is not None:
            probe.append({"counts": list(count), "current": x})
    out = []
    for value in range(k):
        out.extend([value] * count[value])
    return out

Radix sort stacks stable counting sorts, one per digit, least significant first, to handle a wide range with only ten buckets per pass:

def radix_sort(a):
    """O(d * (n + b)) for non-negative integers: sort digit by digit, least-
    significant first, using a STABLE counting sort on each digit. With d digits in
    base b (10 here), it's linear when d is small — how you sort large integers or
    fixed-width keys without a huge count array."""
    if not a:
        return []
    out = list(a)
    place = 1
    while max(out) // place > 0:
        out = _counting_by_digit(out, place)
        place *= 10
    return out


def _counting_by_digit(a, place):
    count = [0] * 10
    for x in a:
        count[(x // place) % 10] += 1
    for d in range(1, 10):
        count[d] += count[d - 1]         # prefix sums → output positions
    out = [0] * len(a)
    for x in reversed(a):                # reversed keeps equal digits stable
        d = (x // place) % 10
        count[d] -= 1
        out[count[d]] = x
    return out

And bucket sort scatters into ranges, sorts each small bucket, and concatenates:

def bucket_sort(a, num_buckets=16):
    """O(n) expected for evenly-spread data: scatter elements into buckets by value
    range, sort each (small) bucket, then concatenate. Fast when the input is
    roughly uniform, because each bucket ends up tiny."""
    if not a:
        return []
    lo, hi = min(a), max(a)
    if lo == hi:
        return list(a)
    span = (hi - lo) / num_buckets
    buckets = [[] for _ in range(num_buckets)]
    for x in a:
        idx = min(int((x - lo) / span), num_buckets - 1)
        buckets[idx].append(x)
    out = []
    for bucket in buckets:
        out.extend(sorted(bucket))       # each bucket is small → cheap
    return out

Watch it work

Here's counting sort tallying twelve values. Each bar is a value; its height is how many times that value has been seen. Step through it and watch the histogram build: each frame reads one input element and bumps its bar (orange) up by one. That's the entire sorting effort — no bar is ever compared to another, they just accumulate. When the scan finishes, reading the bars left to right gives the sorted output directly: all the 1s, then all the 2s, and so on. Sorting by counting, not comparing:

The complete code

Both versions in one place — flip between them. The from-scratch tab has all three linear sorts. The library tab is sorted — a comparison sort, and the baseline these beat on their home turf. This is the rare chapter where the from-scratch code can genuinely out-scale the library, because it exploits a fact about the data (bounded integer keys) that a general sort can't.

"""Non-comparison sorts — counting, radix, and bucket — that beat the O(n log n)
barrier by not comparing elements at all. Any sort that works by comparing pairs
needs at least n log n comparisons; these sidestep that lower bound entirely by using
the keys themselves as array indices. When the keys are bounded integers, they run in
linear time.

The catch is in the "when": they only work on integers (or things you can treat as
integers), and their speed depends on the key range, not just the count.
"""


# region: counting
def counting_sort(a, probe=None):
    """O(n + k) for integers in [0, k): sort by COUNTING, not comparing. Tally how
    many of each value there are, then read the tallies back out in order. There is
    not a single comparison between elements — which is exactly how it dodges the
    O(n log n) comparison bound."""
    if not a:
        return []
    k = max(a) + 1
    count = [0] * k
    for x in a:
        count[x] += 1                    # the whole sort is this tally
        if probe is not None:
            probe.append({"counts": list(count), "current": x})
    out = []
    for value in range(k):
        out.extend([value] * count[value])
    return out
# endregion


# region: radix
def radix_sort(a):
    """O(d * (n + b)) for non-negative integers: sort digit by digit, least-
    significant first, using a STABLE counting sort on each digit. With d digits in
    base b (10 here), it's linear when d is small — how you sort large integers or
    fixed-width keys without a huge count array."""
    if not a:
        return []
    out = list(a)
    place = 1
    while max(out) // place > 0:
        out = _counting_by_digit(out, place)
        place *= 10
    return out


def _counting_by_digit(a, place):
    count = [0] * 10
    for x in a:
        count[(x // place) % 10] += 1
    for d in range(1, 10):
        count[d] += count[d - 1]         # prefix sums → output positions
    out = [0] * len(a)
    for x in reversed(a):                # reversed keeps equal digits stable
        d = (x // place) % 10
        count[d] -= 1
        out[count[d]] = x
    return out
# endregion


# region: bucket
def bucket_sort(a, num_buckets=16):
    """O(n) expected for evenly-spread data: scatter elements into buckets by value
    range, sort each (small) bucket, then concatenate. Fast when the input is
    roughly uniform, because each bucket ends up tiny."""
    if not a:
        return []
    lo, hi = min(a), max(a)
    if lo == hi:
        return list(a)
    span = (hi - lo) / num_buckets
    buckets = [[] for _ in range(num_buckets)]
    for x in a:
        idx = min(int((x - lo) / span), num_buckets - 1)
        buckets[idx].append(x)
    out = []
    for bucket in buckets:
        out.extend(sorted(bucket))       # each bucket is small → cheap
    return out
# endregion

"""There's no non-comparison sort in Python's standard library — `sorted` is Timsort,
a comparison sort. That's the honest counterpart, and the point of the face-off is
that on bounded-integer data, a linear counting or radix sort can actually beat the
O(n log n) library sort — one of the few times hand-rolled code out-scales the
built-in, because it uses a fact about the data (integer keys, bounded range) that a
general comparison sort can't.
"""


# region: sort_builtin
def sort_builtin(a):
    """Timsort — an O(n log n) comparison sort. The general-purpose baseline the
    linear sorts are trying to beat on their home turf (bounded integers)."""
    return sorted(a)
# endregion

Scratch vs library

Counting sort's 3.3× win over Timsort is the headline, and it's real — on bounded integers, a linear tally beats an n log n comparison sort even across the Python/C gap. But radix sort tells the other half of the story: at the same 160000 elements over a wide range it took about 90 ms, slower than Timsort's 12.8 ms, despite also being linear. Why? Its constant. Radix did seven passes (one per decimal digit of a million-range key), each a full counting sort in interpreted Python, and seven Python passes lose to one pass of tuned C. It's the constant-factor lesson from the very first chapter, seen from both sides at once: counting sort wins because its constant is tiny and it does one pass; radix loses because its constant — d Python passes — outweighs its better asymptotic class here. Big-O tells you counting and radix are both linear; the benchmark tells you which linear actually wins.

Where you'll actually meet it

Radix and counting sorts run wherever keys are bounded integers and speed matters. Databases radix-sort integer and fixed-width columns; GPUs use radix sort as their fundamental primitive because it parallelizes beautifully (no comparisons, just bucketing). Counting sort is the standard way to sort by a small categorical key — bin records by status, priority, or day. Bucket sort underlies histogram construction and spatial partitioning. And any "sort these by a byte, a digit, or a small enum" task in performance-critical code is a counting or radix sort in disguise. The comparison sorts are the general tool; these are the ones that make the hot path fast.

Takeaways

The non-comparison sorts — counting, radix, bucket — break the O(n log n) barrier by using keys as indices rather than comparing them, running in $O(n)$ on bounded integers. Counting sort tallies by value ($O(n + k)$, so watch the range k); radix sorts digit by digit to handle wide ranges with small buckets; bucket sort scatters and concatenates for evenly-spread data. They're specialists — strict about their input, unbeatable within it — and counting sort is one of the few places your own code can genuinely beat the library.

That completes the sorting arc — six chapters, from the O(n²) elementary sorts to the provably-optimal O(n log n) comparison sorts to these O(n) specialists. The remaining two chapters of the tier turn from arranging data to finding in it: binary search, which needs data sorted (now you know six ways to get it there), and quickselect, which finds the k-th smallest element in O(n) using the partition from quicksort — without sorting at all.