42Sorting, properly — and a beautiful impossibility

In Chapter 41 we let a function call itself and walk a whole tree of choices to find an answer. Here we ask a colder, sharper question about code you already own. Not how a sort works, but whether it can be beaten. You stepped the five classic sorts line by line in the trace walkthroughs and raced them in the Algorithms Lab. So we skip the how and go straight at the wall — the hard floor every one of them hits — and the one trick that walks clean through it. The whole way, we keep circling the question that turns a coder into a computer scientist: is n log n the best any sort can do, or just the best we've thought of so far? By the end you'll be able to prove, on the back of a napkin, that no sort built from comparisons can ever beat n log n. Then you'll sort a million items in a single linear pass, under that limit, by refusing to compare at all.

01The five sorts share one hidden move

Let's start by lining them all up. Bubble, selection, insertion — the three O(n²) sorts that crawl once the list gets big. Merge and quicksort — the two O(n log n) sorts that win at scale. Five different methods, and the Lab lets you watch each one shuffle the bars into place. But look closely at any of them and the same basic move keeps showing up: pick two items, ask which is bigger, act on the answer. Everything else — the swaps, the splits, the merges — is just bookkeeping wrapped around that one question.

That shared move is the key to the whole chapter. Suppose the only thing your algorithm can ever learn about the data is the outcome of a < b questions. Then the number of questions is the true cost, and there is a hard floor on how few you can get away with. Call any such algorithm a comparison sort. All five of yours are comparison sorts. So is almost every sort you have ever seen.

02The speed limit — and why nobody can break it

Here is the most beautiful argument in this volume, and it is pure counting. Lay out every decision your sort could make as a tree. At the top sits the first comparison it does. Two branches — yes and no — lead to the next comparison, and which one you reach depends on the answer. Keep going. This is a decision tree: internal nodes are comparisons, each edge is an answer, and every path from the top down is one possible run of the algorithm on some input.

Where does a path end? At a leaf — the moment the sort stops asking and commits to an output order. Now the punch line. A list of n distinct items has n! possible starting arrangements (n choices for first, n−1 for second, and so on), and each one needs a different reshuffle to come out sorted. So the tree must have at least n! leaves — one distinct verdict per arrangement. Miss even one, and there is an input your sort gets wrong.

Now weigh the tree. Each comparison drops you one level. So the height of the tree — the longest root-to-leaf path — is the worst-case number of comparisons. And a binary (yes/no) tree of height h can hold at most 2ʰ leaves: 2 at depth 1, 4 at depth 2, doubling each level. Put the two facts together:

Read what just happened. We never named a specific algorithm. We just said this: whatever your comparison sort is — one you know, one you will invent, one no human has thought of yet — it is some decision tree. And every decision tree that sorts n items is at least log₂(n!) levels tall. That is why n log n is not "the best we have managed." It is the best that can exist. Merge sort already sits on that floor, and you cannot pay less.

The numbers are concrete and I checked each one in Python. To sort 3 items you need at least ⌈log₂ 6⌉ = 3 comparisons; 5 items, at least 7; 12 items, at least 29; 100 items, at least 525. And log₂(n!) hugs n log₂ n so tightly that by a million items the floor is already 93% of it — same curve, same Θ(n log n) band, forever.

The floor only holds if you insist on comparing. What if the values could tell you where they belong — without a single comparison? →

03Walk through the wall — counting sort

Suppose you are sorting a million song ratings, each an integer from 0 to 5. The comparison floor says n log₂ n ≈ 20 million questions. But you never need a question. A rating of 5 doesn't need to be compared with anything — it just is a 5, and you already know exactly where all the 5s go: after the 4s, before nothing. The value is its own address.

That is counting sort. Make one tally box per possible value. Walk the data once, dropping each item into its box. Then walk the boxes in order, pouring them back out. No item is ever weighed against another. Here it is, and it really runs:

def counting_sort(a, k):        # every value is an int in range 0..k-1
    count = [0] * k             # one tally box per possible value
    for x in a:                 # PASS 1 - n steps: tally each item
        count[x] += 1           #   the value IS the index. no comparison.
    out = []
    for v in range(k):          # PASS 2 - k steps: walk boxes in order
        out.extend([v] * count[v])   # pour box v back out, count[v] times
    return out

print(counting_sort([3,1,4,1,5,9,2,6,5,3,5,0,7,2,6], 10))
# [0, 1, 1, 2, 2, 3, 3, 4, 5, 5, 5, 6, 6, 7, 9]   <- matches sorted()

Line by line: count = [0]*k builds k empty boxes. The first loop runs n times — count[x] += 1 uses the value x directly as an array index (Volume 1: indexing a list is O(1), a straight jump to a memory address). The second loop runs k times, emitting each value as many times as it was tallied. Total work: n + k. I ran it against Python's sorted() on the same data — identical output.

When k is small next to n, this is linear — it slips under the comparison floor as if the floor isn't there. I measured the op counts: a million items with values in 0–255 costs about 1,000,256 steps, where a comparison sort would spend ~20 million — roughly 20× fewer. There is no contradiction with the last section. The floor was proven for sorts that only compare. Counting sort never compares. Different game, different rules.

The price is written in the method. You need k boxes, so the values must be bounded integers (or things you can map to a small integer range) — you cannot counting-sort arbitrary floats or strings this way — and you pay O(k) memory for the boxes. Push k up toward "any 64-bit integer" and you would need billions of boxes; the trick collapses. Counting sort wins precisely when the range of values is small, whatever the count.

Bounded to 0–5 is easy. But a million distinct 9-digit ID numbers? That is k = a billion boxes. There is a way to keep the linear speed anyway — sort them one digit at a time. →

04Radix sort — counting, one digit at a time

Big numbers break counting sort because their range is huge. But each individual digit has a tiny range — 0 to 9. So sort by the last digit, then the next, up to the first, using a stable counting sort on each pass. After the final digit, the whole list is sorted. This is radix sort, and it is exactly how the old punched-card machines physically sorted — a fact we'll come back to.

def radix_sort(a):
    m = max(a)
    exp = 1
    while m // exp > 0:              # one pass per digit of the biggest number
        a = counting_by_digit(a, exp)   # stable counting sort on this digit
        exp *= 10                    # move to the next digit up
    return a

print(radix_sort([170, 45, 75, 90, 802, 24, 2, 66]))
# [2, 24, 45, 66, 75, 90, 170, 802]   <- matches sorted()

The loop runs once per digit — call that d passes — and each pass is a counting sort over ten boxes, costing O(n + 10). Total: O(d·(n + 10)), which for fixed-width keys is just O(n). I ran it against sorted(), and the outputs match. The whole thing works only because each pass is stable: it never disturbs the order the earlier passes established. That word, stable, is carrying a lot of weight here, so it gets its own section next.

Everything in radix hangs on one promise: equal-keyed items keep their order across passes. Break that promise and the whole scheme scrambles. Time to make it precise. →

05Stability — when equal keys must keep their order

A sort is stable if, when two items compare equal on the sort key, they come out in the same order they went in. Unstable sorts are free to shuffle ties. It sounds like a technicality. It is the difference between a spreadsheet that does what you meant and one that quietly corrupts your data.

Why it matters: it is how you sort by two keys. Say you want your playlist grouped by artist, and within each artist, ordered by length. Sort by the secondary key first (length), then by the primary key (artist) with a stable sort — the stable pass keeps the length-order intact inside each artist group. I ran exactly this:

songs = [("Levels","Avicii",200), ("Wake Me Up","Avicii",247),
         ("Titanium","Guetta",245), ("Without You","Guetta",210),
         ("Hey Brother","Avicii",254)]

step1 = sorted(songs, key=lambda s: s[2])   # first by seconds (secondary key)
step2 = sorted(step1, key=lambda s: s[1])   # then by artist (primary), STABLE

# ('Levels','Avicii',200) ('Wake Me Up','Avicii',247) ('Hey Brother','Avicii',254)
# ('Without You','Guetta',210) ('Titanium','Guetta',245)

Read the result: the Avicii block is internally sorted by seconds (200, 247, 254) and the Guetta block too (210, 245) — even though the second sort only looked at artist. The stable pass never touched the ties, so the first sort's work survived underneath it. Two stable sorts in a row give you a two-level ordering, for free. An unstable sort would have jumbled the seconds within each artist, and you'd have to sort with a compound key instead.

Python's sorted() is stable, and I have been leaning on that all chapter. But what is sorted()? It isn't plain merge sort. It is something cleverer — and it gets suspiciously fast on data that is already a bit sorted. →

06What sorted() actually runs — Timsort

Real data is rarely random. Logs arrive almost in time order; a list you append to and re-sort is mostly sorted already; sensor readings drift. Timsort — the algorithm behind Python's list.sort() and sorted() — is built around that observation. It is a merge sort / insertion sort hybrid that first scans for runs: stretches already in order. Every run it finds is work it doesn't have to do. Then it merges the runs, using insertion sort to tidy short pieces and clever "galloping" to skip through long ones.

The consequence is dramatic, and I timed it on this machine (best of 5 runs, a million floats — treat the milliseconds as indicative, not exact):

n = 1_000_000                       # sorted() on different input orders
# random order    :  146.1 ms       <- the full n log n price
# already sorted  :    9.6 ms       <- ~15x faster: one giant run, near-linear
# reverse sorted  :   10.9 ms       <- ~13x faster: spots the descending run, flips it
# 20 sorted runs  :   10.6 ms       <- ~14x faster: merges 20 pre-made runs

On already-sorted data Timsort makes essentially one pass, confirms the whole list is one long run, and stops — O(n), not O(n log n). Reverse-sorted is nearly as fast: it spots a strictly descending run and reverses it in place. That is why re-sorting a list you just tweaked is almost free. The general bound is O(n log r), where r is the number of runs. When the data is one big run (r = 1), that collapses to O(n). When it's fully scrambled (r ≈ n), you pay the full n log n. It never beats the comparison floor on random data — the last section forbids that — but it collects every scrap of existing order.

Sorting arranges data so you can find things fast — the next chapter is about the finding itself: searching & selection. How binary search pinpoints any item in a sorted array in O(log n) by halving the haystack instead of scanning it — and how the same halving idea plucks the median out of a billion numbers without ever sorting them. →