Sorting Is the Cheapest Structure: The Comparison Lower Bound, Counting Sort, and Binary Search

Part one was about reading $n$ and knowing which complexity to write. This part covers CPHB chapter 3: sorting. It’s a short chapter, but it hides an idea I find more important than any sorting algorithm — sorting isn’t the goal, it manufactures structure for the problems that come after. A lot of problems are hard only because the elements are in no particular order; once sorted, duplicates sit next to each other, things that belong together become neighbours, and whatever you’re looking for can be closed in on with binary search. You pay $O(n \log n)$, and every step after that gets cheaper.

The post follows the book’s three sections: the theory (why $n \log n$, and when you can do better), using it in code (the book does C++; here it’s Python), and binary search.

Why n log n

Start with the dumbest one: bubble sort, one inversion per swap

The book opens with bubble sort — $n$ rounds, each sweeping left to right and swapping any adjacent pair that’s out of order:

for i in range(n):
    for j in range(n - 1):
        if array[j] > array[j + 1]:
            array[j], array[j + 1] = array[j + 1], array[j]

Two nested loops, $O(n^2)$. But the book follows it with a lovely argument for why every sort that only swaps adjacent elements is at least $O(n^2)$. The tool is the inversion: a pair of positions $a < b$ with $\text{array}[a] > \text{array}[b]$ — an earlier element that’s larger than a later one. The number of inversions measures how far the array is from sorted: sorted means 0, fully reversed means $n(n-1)/2$.

The key sentence: swapping two adjacent elements removes exactly one inversion. No more, no less. So if adjacent swaps are all you have, the worst case needs $n(n-1)/2$ of them — and that’s where $O(n^2)$ comes from.

The meter in the animation shows “inversions left”. Step through a few: it only drops on a swap step, and it always drops by exactly one.

To go faster, remove many inversions at once: merge sort

An $O(n \log n)$ sort isn’t bound by “adjacent swaps only”. The book’s representative is merge sort, and its shape is recursion:

1. A single element needs no work.
2. Split in the middle.
3. Sort each half recursively.
4. Merge the two sorted halves — since both are in order, merging takes $O(n)$ (two pointers walking right, always taking the smaller).

Each level of recursion halves the range, so there are $O(\log n)$ levels; the merging on each level adds up to $O(n)$. Multiply and you get $O(n \log n)$. One merge can carry an element past many others at once — that’s why it kills inversions faster than bubble sort.

The lower bound: if you compare, you can’t escape n log n

Can anything beat $n \log n$? The book gives a compact proof: not as long as your sort works by comparing elements.

Think of sorting as a decision tree: each node asks ”$x < y$?” and goes left or right; at a leaf, you know how these $n$ elements are ordered. $n$ elements have $n!$ orderings, so the tree needs at least $n!$ leaves, which makes its height at least $\log_2(n!)$. And $\log_2(n!) \ge (n/2)\log_2(n/2)$, which is roughly $n \log n$. The height of the tree is the worst-case number of comparisons — lower bound proved.

What’s nice about this proof is that it’s algorithm-agnostic. It doesn’t say “merge sort can’t get faster”; it says “nothing that compares can get faster”.

Around the bound: counting sort, no comparisons, no limit

The bound assumes comparisons. Skip them? Counting sort uses each element’s value as an index: allocate a count array, count how many times each value appears in one pass, then write them back out in index order in a second pass. $O(n)$, provided the elements are integers in $0 \ldots c$ with $c = O(n)$ — the count array has to fit.

Look at the state right after the first pass: the count array is already a compressed form of the sorted array — how many of each value. The second pass just unpacks it. It’s fast because it uses a piece of information comparison sorts never touch: the value itself is the position. The price is that the information has to exist in the first place (integers, small range); without it there’s nothing to use.

Sorting in Python

The book is blunt: you almost never write your own sort in a contest. The standard library’s sort is fast and correct, and yours won’t be better. The book talks about C++‘s sort; in Python that’s sorted and list.sort — Timsort underneath, stable, $O(n \log n)$, and implemented in C, which makes it far faster than any sort you’d write in a Python loop.

v = [4, 2, 5, 3, 5, 8, 3]
sorted(v)                        # [2, 3, 3, 4, 5, 5, 8], returns a new list
v.sort()                         # in place
v.sort(reverse=True)             # descending
"".join(sorted("monkey"))        # strings sort too: "ekmnoy"

Sorting your own things works differently from C++: C++ hands sort a function that compares two elements, Python hands sorted a key — what to sort each element by. Three routes:

Approach	When
Sort directly; tuples compare element by element (first field, then second on ties)	Most cases. For “by A, then by B”, pack the data into tuples: sorted(pairs)
key=lambda x: (len(x), x)	Same type, different order — e.g. strings by length first, then lexicographically. A key returning a tuple is a multi-level sort key
Define __lt__ on the class	Your own type, with exactly one natural order

words = ["banana", "kiwi", "apple", "fig"]
sorted(words, key=lambda w: (len(w), w))     # ['fig', 'kiwi', 'apple', 'banana']
sorted(words, key=len, reverse=True)         # longest first

The key design sidesteps the classic C++ comparator trap: a comparator must be a strict weak ordering, a < a has to return false, and writing it with <= produces garbage on certain inputs. A key only maps each element to another value and compares with the built-in <, so an inconsistent order is impossible to write. If you really need the old “compare two elements” form, functools.cmp_to_key converts it — but you almost never will.

Binary search

Finding x in a sorted array

In an unsorted array, finding a value means checking cells one at a time, $O(n)$ — nothing tells you where to look. Once sorted, the order itself is the navigation. Binary search checks the middle cell each step: equal means found; larger than $x$ means the whole right half can be skipped; smaller means the whole left half can.

a, b = 0, n - 1
while a <= b:
    k = (a + b) // 2
    if array[k] == x:
        return k          # found
    if array[k] > x:
        b = k - 1
    else:
        a = k + 1

The “still possible” region $a \ldots b$ halves every step, hence $O(\log n)$. Below it runs side by side with a linear scan, one comparison per step on each side. Watch the blue region on the right shrink — and the faded cells on the left, which are what the linear scan has “ruled out”, growing by one cell per step.

At $n = 9$ it’s 8 against 3. At $n = 10^6$ it’s up to $10^6$ against at most 20.

The book also gives a second form: start from the left and jump, with a jump length that starts at $n/2$ and halves each round — jump if you can, shrink the stride if you can’t. Still $O(\log n)$, but with no notion of “the middle”, and it comes back when we do binary lifting on trees (part 16).

k = 0
b = n // 2
while b >= 1:
    while k + b < n and array[k + b] <= x:
        k += b
    b //= 2
if array[k] == x:
    pass                  # found, at k

The standard library has it too, in the bisect module: bisect_left (the first position with value $\ge x$, C++‘s lower_bound) and bisect_right (the first position with value $> x$, C++‘s upper_bound). Their difference is how many times $x$ occurs:

from bisect import bisect_left, bisect_right
count = bisect_right(array, x) - bisect_left(array, x)

The real binary search: binary search on the answer

This section is the most valuable part of the chapter.

What binary search actually needs is not a sorted array but a monotone predicate $\text{ok}(x)$: over the answer space, a run of false followed by all true. As long as that shape holds, the same halving finds the first true — which is usually “the smallest feasible answer”.

The book’s version uses the jumping form:

x = -1
b = z
while b >= 1:
    while not ok(x + b):
        x += b
    b //= 2
k = x + 1        # the smallest k with ok(k) true

$z$ has to be large enough that $\text{ok}(z)$ is known to be true. Every call to $\text{ok}$ halves the range, so there are $O(\log z)$ calls in total; the overall complexity depends on what $\text{ok}$ itself costs — an $O(n)$ $\text{ok}$ makes the whole thing $O(n \log z)$.

This idea turns many “find the smallest / largest X” problems into “decide whether X works”: deciding is usually much easier than solving, and binary search is what turns the decision into the solution. The same section notes that a function that rises and then falls can be binary-searched too (find the last $x$ with $f(x) < f(x+1)$), but adjacent values must not be equal, or you can’t tell which way to go.

What got wasted

• bubble sort → merge sort: a swap moves two adjacent elements and removes one inversion; a merge carries an element past a whole run at once.
• comparing → counting: a comparison sort only uses “which is bigger”; counting sort uses “the value is the position”, which is how it gets under the $n \log n$ bound — provided that information exists.
• linear scan → binary search: a linear scan rules out one cell per step; once sorted, one comparison rules out half.

All three are the same move: find an order the brute-force solution never used. This post’s structure tags are [order] — sort things first, or notice the answer space is already ordered — and [monotone]: every step of a binary search closes in from one direction only.

Where this shows up at work

• A database index is “sort, then binary search”. B-tree leaves are ordered, so an equality lookup is a binary search closing in, and range queries, ORDER BY and prefix LIKE all benefit — the post on indexes is really this chapter. An LSM tree’s SSTables are sorted before they’re written, and the compaction merge is merge sort’s merge.
• Binary search on the answer is everywhere in engineering. git bisect is binary search over commit history with the predicate “is this version broken?”; a load test looking for a system’s ceiling is binary search over QPS with the predicate “does it hold at this rate?”. As long as the predicate is monotone, you don’t try values one by one.
• Sorting first often beats a set. The book’s next chapter makes the point: for many “find duplicates, find pairs, count frequencies” problems, sorting the array and scanning it once is faster and leaner than throwing it into a hash structure — smaller constants, cache-friendly. The next post expands on it.

Reflections

Sorting pays on behalf of everyone who comes after

Last time I said the thing I use most at work is estimation — reading the size of the data to decide whether a computation is viable. Sorting is the item that shows up most often in that estimate: on a table of a few million rows, “sort first, then process” versus “look each one up” is routinely the difference between seconds and hours. An index is, at bottom, the database doing that sort for you ahead of time — and keeping it maintained.

This chapter let me say it more cleanly: sorting costs $n \log n$, and what it buys is that every query after it becomes $\log n$. Query once and it’s not worth it; query many times and sorting is the cheapest investment there is. It’s also why, when I see code doing a linear search over the same data inside a loop, my first reaction isn’t “pick a different data structure” — it’s “sort it first”.