Linear-Time Sorts

Breaking the rules on purpose

The Merge Sort lesson proved that no algorithm sorting by comparisons can beat Ω(n log n) in the worst case. That proof's power came entirely from its assumption — "the only thing the algorithm can do is ask is A < B?." Drop that assumption, and the proof simply doesn't apply. This lesson's sorts don't compare elements to each other at all; they exploit structural knowledge about the values themselves — and that's precisely what lets them run in O(n).

Counting sort: when values are small integers

If every value is a small integer in a known range [0, k], you don't need to compare anything — you can count directly:

def counting_sort(arr: list[int], k: int) -> list[int]:
    counts = [0] * (k + 1)
    for x in arr:
        counts[x] += 1                # tally each value — Module 6's Count verb
    result = []
    for value, count in enumerate(counts):
        result.extend([value] * count)   # emit each value 'count' times, in order
    return result

This is Hash Tables' Count pattern from Module 6, applied to sorting: tally every value's frequency, then read the tallies out in order. No comparison ever happens — the ORDER comes from iterating the counts array 0, 1, 2, …, k, which is only possible because the values are small integers you can use as array indices.

Think of it like sorting mail into a wall of labeled pigeonholes, one hole per possible value: drop each letter straight into its hole (no comparing letters to each other), then walk the wall left to right and empty each hole in turn. The order was never "figured out" — it's just where the wall already put things.

The catch is exactly what makes it fast: k must be small relative to n. Counting-sorting values up to 10⁹ would allocate a billion-entry array to sort a handful of numbers — the technique needs a bounded, usefully small range, not just "integers."

Radix sort: sort digit by digit, when k is too large

When values are large integers but you still want to avoid comparisons, sort by one digit at a time — least significant digit first — using counting sort as the per-digit subroutine:

def radix_sort(arr: list[int]) -> list[int]:
    if not arr:
        return arr
    max_val = max(arr)
    exp = 1
    result = list(arr)
    while max_val // exp > 0:
        result = counting_sort_by_digit(result, exp)
        exp *= 10
    return result

def counting_sort_by_digit(arr: list[int], exp: int) -> list[int]:
    counts = [0] * 10
    for x in arr:
        counts[(x // exp) % 10] += 1
    for d in range(1, 10):
        counts[d] += counts[d - 1]        # prefix sum -> final positions
    result = [0] * len(arr)
    for x in reversed(arr):               # reversed: keeps it STABLE
        digit = (x // exp) % 10
        counts[digit] -= 1
        result[counts[digit]] = x
    return result

The per-digit pass is a prefix-sum-positioned counting sort (Module 12's prefix sums, placing each element directly into its final slot instead of just emitting counts in order) — and it must be stable, because sorting by the next digit only produces a correct overall order if ties from the previous digit stay in their relative order. Walking the array in reverse while placing (rather than forward) is what makes this particular implementation stable — trace two equal last-digits through it once to see why order survives: arr = [13, 23, 7], digit = ones place (exp = 1). Digits are 3, 3, 7; prefix-summed counts give slot 1 for the last "3" placed and slot 0 for the one placed before it. Iterating in reverse means 7 (index 2) is placed first at its slot, then 23 (index 1) claims the LAST available "3" slot, then 13 (index 0) claims the slot before it — landing 13 ahead of 23 in the result, preserving their original relative order even though both have the same ones digit. Iterating forward would have handed the later slot to whichever "3" was seen first — the wrong element for a stable sort.

Full trace, both passes, on arr = [29, 13, 22, 19, 5]: ones-digit pass (digits 9, 3, 2, 9, 5) produces [22, 13, 5, 29, 19] — the two 9s (29, 19) keep their original relative order. Tens-digit pass on that result (digits 2, 1, 0, 2, 1) produces [5, 13, 19, 22, 29] — fully sorted, in two linear passes over five elements, no comparisons made.

Think of it like sorting index cards into bins by their last digit first, then re-sorting the (already ones-sorted) stack into bins by their tens digit, always keeping each bin's incoming order intact as you place cards into it — by the time the most significant digit's pass finishes, every earlier digit's ordering is still baked in.

Reading which sort a problem wants

In practice, you will almost always call the language's built-in sort — Python's Timsort and JS's engine sort are both highly-tuned hybrids (insertion sort for small runs, merge-sort-like merging of already-sorted runs, stable). Knowing the theory here isn't about reimplementing sorts daily; it's about knowing which GUARANTEE you're actually getting when you call sorted() or .sort() — stable, O(n log n) worst case, not in-place — and recognizing the rare problems (bounded small-integer keys, custom multi-key comparisons) where a hand-written sort is the actually-correct engineering choice.