Counting Sort vs Radix Sort: Sorting Without Comparisons

Every sort built on comparing two elements needs O(n log n) comparisons in the worst case. That lower bound is real — but it only covers comparison sorts. Counting sort and radix sort never compare two elements. They read keys as numbers and use them as array positions, which lets them run in linear time on the right kind of data. The two are usually taught separately, but radix sort is really counting sort applied one digit at a time.

The problem it solves

Sorting a million exam scores between 0 and 100, or a list of ages, or two-byte codes, with a general-purpose sort does work that the data does not need: the keys come from a small, known range. Counting sort turns that range into an array of counters and sorts in O(n + k), where k is the number of possible key values.

When the range is too large for one array of counters — 32-bit IDs, say — radix sort splits each key into digits and runs one counting pass per digit.

The intuition

Counting sort has three steps:

• Tally: walk the input and count how many times each key appears.
• Prefix sums: turn the counts into starting positions. If there are two 0s and one 1, the 0s go in slots 0 and 1, and the 1 starts at slot 2.
• Place: walk the input again, in its original order, and put each item at its key's next free slot.

The third step is what makes the sort stable: items with equal keys come out in the order they went in. For bare integers that does not matter. For records sorted by one field — orders sorted by priority — it does. And it is the whole reason radix sort works.

Radix sort sorts by the last digit first, then by the second-to-last, and so on up to the most significant digit. After the pass on digit d, numbers are sorted by their last d digits. The next pass sorts by a more important digit, and when two numbers tie on it, stability keeps them in the order the earlier passes established. After the last pass, the whole number is sorted.

Watch it run

The animation sorts seven values from 0 to 3. Each value drops into its own bucket with no comparison, and one pass gives the tally [1, 2, 1, 3]. Then the buckets are read back out in order: 0 once, 1 twice, 2 once, 3 three times. Nothing was ever compared with anything.

The code

A stable counting sort that takes a key function, so it can sort records as well as numbers, and a radix sort built on top of it:

def counting_sort(items, key, k):
    """Stable sort of items by key(item), an integer in range(k)."""
    count = [0] * k
    for x in items:
        count[key(x)] += 1                     # 1. tally each key
    start, total = [0] * k, 0
    for v in range(k):
        start[v], total = total, total + count[v]   # 2. first slot for each key
    out = [None] * len(items)
    for x in items:                            # 3. place, in input order
        out[start[key(x)]] = x
        start[key(x)] += 1
    return out

orders = [("ana", 2), ("ben", 0), ("cem", 2), ("dia", 1), ("eli", 0)]
print(counting_sort(orders, key=lambda o: o[1], k=3))
# [('ben', 0), ('eli', 0), ('dia', 1), ('ana', 2), ('cem', 2)]

def radix_sort(nums, base=10):
    """LSD radix sort for non-negative integers: one stable pass per digit."""
    place, passes = 1, 0
    while nums and place <= max(nums):
        nums = counting_sort(nums, key=lambda x: x // place % base, k=base)
        place *= base
        passes += 1
    return nums, passes

print(radix_sort([170, 45, 75, 90, 2, 802, 24, 66]))
# ([2, 24, 45, 66, 75, 90, 170, 802], 3)
print(radix_sort([170, 45, 75, 90, 2, 802, 24, 66], base=256))
# ([2, 24, 45, 66, 75, 90, 170, 802], 2)

The orders keep their original sequence within each priority: ben before eli, ana before cem. With base 10, the numbers up to 802 need three passes; with base 256 — one byte per "digit" — they need two. A larger base means fewer passes but a larger count array per pass.

Now break stability on purpose. This pass uses the same buckets but puts each new item at the front of its bucket, so ties come out reversed:

def unstable_pass(nums, key, k):               # same buckets, ties come out reversed
    buckets = [[] for _ in range(k)]
    for x in nums:
        buckets[key(x)].insert(0, x)
    return [x for b in buckets for x in b]

def radix_unstable(nums):
    place = 1
    while nums and place <= max(nums):
        nums = unstable_pass(nums, lambda x: x // place % 10, 10)
        place *= 10
    return nums

print(radix_unstable([12, 15, 21]))           # [15, 12, 21]

The first pass correctly orders 12 before 15 by their last digit. The second pass sees them tie on the tens digit and reverses them, undoing the first pass's work.

Finally, both sorts are checked against Python's sorted on 2,000 random lists, with values up to 9, 999 or a million. The counting sort check sorts by last digit only, so there are many ties and stability is actually tested — sorted is stable too, so the two must agree exactly:

import random

random.seed(9)
ok, unstable_wrong = True, 0
for _ in range(2000):
    nums = [random.randint(0, random.choice([9, 999, 10**6])) for _ in range(random.randint(0, 40))]
    ok &= counting_sort(nums, key=lambda x: x % 10, k=10) == sorted(nums, key=lambda x: x % 10)
    ok &= radix_sort(nums)[0] == sorted(nums) == radix_sort(nums, base=256)[0]
    unstable_wrong += radix_unstable(nums) != sorted(nums)
print(ok, unstable_wrong)                      # True 1796

The stable versions match every time. The unstable radix sort fails on 1,796 of the 2,000 lists.

The complexity

Counting sort makes two passes over the n items and one over the k counters: O(n + k) time and O(n + k) extra space. It is linear only while k is not much bigger than n. Sorting ten numbers drawn from a range of a billion would allocate a billion counters.

Radix sort runs d counting passes, where d is the number of digits in base b: O(d · (n + b)) time and O(n + b) space. For fixed-width keys — 32-bit integers in base 256 never need more than four passes — that is linear in n. Comparison sorts still win for short lists, for keys with no natural digits, and when memory matters, since both of these sorts need an output array.

Where it goes wrong

• Huge or unknown ranges. Counting sort needs k counters. Check the range first, or use radix sort.
• Negative numbers. Neither version above handles them. For counting sort, subtract the minimum from every key. For radix sort, sort the negatives and non-negatives separately, or flip the sign bit of fixed-width integers.
• An unstable digit pass. Shown above: every pass after the first can destroy the order earlier passes built.
• Starting from the most significant digit. MSD radix sort exists, but it has to sort each bucket separately and recursively. Sorting the whole list by the most significant digit and then by the next one does not work.

How to say it in an interview

"Counting sort tallies how often each key occurs, turns the tallies into starting positions with prefix sums, and places items in input order, so it's stable and runs in O(n + k). It beats the n log n bound because it never compares elements, but only when the key range k is small. Radix sort extends it to large integers by running a stable counting sort on each digit, least significant first; stability is what keeps the earlier digits' order. That's O(d · (n + b))."

The per-digit passes are animated in the radix sort lesson, and which sort when compares them with the comparison sorts.