Counting & Radix Sort

Every sort you have met so far — bubble, merge, quick — works by comparing elements. There is a clever lower bound that says comparison sorts can never beat O(n log n). Counting sort sidesteps that entirely: it never compares two values. Instead it asks, for each possible value, how many times do you appear? — and then writes the answer out in order. When the values come from a small range, this runs in plain linear time.

Intuition

Imagine sorting a deck of cards numbered 0 to 5. You would not bubble them around — you would deal them into six piles, one pile per number, then stack the piles up in order: all the 0s, then the 1s, then the 2s, and so on. You never compared two cards to each other; you only ever looked at a card and dropped it on the matching pile.

The count array is exactly those six piles, except instead of physically holding cards we just keep a running tally of how big each pile is.

Walk through it

The animation on the right shows three rows. The top row is the input [2, 5, 3, 0, 2, 3, 0, 3]. The middle row is the count array — six buckets, one per value 0..5, all starting at zero.

In the first phase we sweep the input left to right. Each element lights up, and the bucket for its value ticks up by one. After eight ticks the buckets read [2, 0, 2, 3, 0, 1]: two 0s, no 1s, two 2s, three 3s, no 4s, one 5.

In the second phase we read the buckets in value order and fill the output row at the bottom. Bucket 0 holds 2, so we write 0 twice; bucket 1 holds 0, so we skip 1 entirely; bucket 2 writes 2 twice; and so on. The output fills up as [0, 0, 2, 2, 3, 3, 3, 5] — sorted, without a single comparison.

The code, line by line

def counting_sort(a, k):
    # k = max value + 1; here values are 0..5 so k = 6
    count = [0] * k
    output = [0] * len(a)
    for num in a:          # tally pass
        count[num] += 1
    i = 0
    for v in range(k):     # write-back, in value order
        for _ in range(count[v]):
            output[i] = v
            i += 1
    return output

• count = [0] * k makes one bucket per possible value. This is where the k in O(n + k) comes from.
• The tally pass (lines 5-6) is the only time we touch the input. Each count[num] += 1 is a single array bump — no scanning, no comparing.
• The write-back (lines 8-11) walks the buckets in increasing value order. The inner for _ in range(count[v]) emits the value v exactly count[v] times, so a value that appeared three times gets written three times.
• Buckets with a count of 0 make the inner loop run zero times, so absent values cost nothing.

Radix sort: counting sort, digit by digit

Counting sort needs a small value range — making a billion buckets to sort a few large numbers is absurd. Radix sort fixes this by sorting on one digit at a time, least-significant digit first (LSD), using counting sort (which is stable) as the inner step. Each pass has only 10 buckets (digits 0..9), and after d passes the numbers are fully sorted.

def radix_sort(a):
    digit = 1
    while max(a) // digit > 0:          # one pass per digit
        buckets = [[] for _ in range(10)]
        for num in a:
            buckets[(num // digit) % 10].append(num)   # stable counting sort by this digit
        a = [num for b in buckets for num in b]
        digit *= 10
    return a

Because each digit pass is stable, sorting by the ones digit, then the tens, then the hundreds leaves the array fully sorted. For d-digit numbers this is O(d · (n + 10)) — effectively linear when d is small.

Complexity

Counting sort is linear when k (the value range) is comparable to n. The space is O(n + k): the count buckets plus the output array. That extra memory is the trade you make for beating the O(n log n) comparison-sort barrier.

When to use / pitfalls

Practice