The sorting tournament

In the last chapter breadth-first search found the metro route with the fewest stops. A navigation app needs more than that: roads have lengths, and BFS can’t see them. Before we teach a machine to weigh roads, we need two skills that nearly every program with data relies on, navigation apps included: finding things fast and putting them in order. A navigation app finds a street among hundreds of thousands of names in a blink because the names are kept in alphabetical order, and it lists routes from fastest to slowest, so it sorts those too. This chapter is a tournament. The contestants step into the ring one at a time, each with a counter of comparisons, and at the end the judge will announce a limit that nobody can get past. You go first.

Round one: a human

In front of you lie five cards, face down. Each has a number on it, but you are not allowed to turn them over. You may point at two of them and ask the judge which number is greater. Each such question is one comparison, and a counter keeps track of them. Your job is to find out the order of the numbers with as few questions as possible. So that you don’t have to keep the answers in your head, you can move the cards with your finger or the mouse and lay them out as you guess: moving is free, you pay only for questions.

How many questions did it take you? Nine or ten is a typical first game, eight is a good one. Play a couple more times: can you do it in seven?

Keep an eye on the bar under the cards. Five different numbers can be laid out in a row in $5! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120$ ways (where the factorial comes from is explained in “Mathematics, the Queen of the Sciences”), and at the start of the game any of them is possible. Each of the judge’s answers crosses out the orders that contradict it. A good question crosses out half, a poor one fewer. And sometimes a question crosses out nothing: its answer followed from the earlier ones, and the comparison was wasted. The game ends when a single order is left, and then the cards are turned over.

After the game a score appears under the bar: how many comparisons the algorithms that come into the ring next would make on the same deck. A human is a strong player: you remember every answer and invent clever questions on the fly. But for a million cards no human has the patience. An algorithm has patience to spare, but it can’t invent anything; it only follows its rule. And like you, it learns about the data only from comparisons: each one answers the question “less or not?” and nothing more. The machines come next, each with a single rule.

Round two: selection

The first strategy is the one a gym teacher uses to line up a class by height: find the shortest child and put them first, then the shortest of the rest second, and so on to the end. This is selection sort. A slider will appear under the cell, and frame by frame you can watch the finished part grow.

How many comparisons is that? To find the smallest of $n$ items, the candidate has to be compared with each of the others, which is $n - 1$ comparisons. Then the smallest of the $n - 1$ that remain, another $n - 2$, and so on:

$$(n-1) + (n-2) + \ldots + 2 + 1 = \frac{n(n-1)}{2}.$$

That is the number of pairs you can make from $n$ items, although selection doesn’t go through pairs: it compares each item with the current candidate, and on the list [2, 3, 1] it compares 2 and 3 twice and 1 and 3 never. A thousand numbers take almost half a million comparisons, a million take half a trillion. On five cards selection asks ten questions, so you have most likely beaten it already. Worse, the number doesn’t depend on the data. Selection works as hard on a list that is already sorted: to be sure the first item is the smallest, it has to examine all the others, and it has no way of remembering what it learned on earlier passes.

On the other hand, selection makes few swaps, at most $n - 1$, one per position. When moving things costs far more than comparing them (shifting heavy crates around a warehouse while checking the labels, say), that is its trump card.

Round three: insertion

A card player sorts a hand differently. He picks up the cards one at a time and slips each one into its place among those already in his hand. The left part of the hand is always in order, and a new card travels left until it meets a card no bigger than itself. This is insertion sort.

Press “Steps” and watch the while loop: it stops as soon as the card to the left is no bigger than the new one. So the work insertion does depends on how shuffled the data is. Here are its comparisons, counted on three lists of a thousand numbers.

On a sorted list, 999 comparisons, one per card: each card sees at once that it is in place. On a reversed list, 499,500, which is $\frac{n(n-1)}{2}$, the same as selection: every new card travels all the way to the front. On a shuffled list, about a quarter of a million, roughly $n^2/4$: on average a card travels half the hand. The best and worst cases of Chapter 13 are a whole order of growth apart here: $\Theta(n)$ against $\Theta(n^2)$.

What does the work of insertion measure? Call an inversion a pair of items that are out of order: the larger on the left, the smaller on the right. Every shift in the while loop swaps one such pair, a pair of neighbors, and touches nothing else. So there are as many shifts as the list has inversions, and no more comparisons than inversions plus $n - 1$. In a nearly sorted list, where only a few cards are out of place, inversions are few, and insertion gets through in almost linear time. That is why it is used for short and nearly sorted lists; Python’s built-in sort uses it for short stretches too.

An improvement suggests itself. The left part of the hand is sorted, so the place for the new card can be found by binary search (more about it below): $\log_2 i$ comparisons instead of $i$. The comparisons drop to about $n \log n$. But finding the place is not enough: the card has to be put there, and that means shifting everything bigger one step to the right. At the start of Chapter 17 we inserted numbers this way with bisect.insort and saw that twice as many numbers took four times as long. The square didn’t go anywhere; it moved from the comparisons to the shifts.

Round four: bubble

You saw bubble sort in the race in Chapter 0. It walks along the list and swaps neighbors that are out of order; in one pass the largest item “bubbles up” to the end, like a bubble in water. We add one precaution: if a whole pass made no swaps, the list is already sorted and we can stop.

Bubble sort swaps only neighbors, so, like insertion, it fixes the inversions one at a time: it makes as many swaps as insertion makes shifts. But it usually makes more comparisons, and each swap writes to the list twice, while a shift in insertion writes once. It also has an odd asymmetry: a big item at the front of the list rides to the end in a single pass, while a small item at the end moves left only one position per pass. The list [2, 3, 4, 5, 6, 1] is nearly sorted, yet bubble sort needs five passes on it.

In the third volume of The Art of Computer Programming Donald Knuth passed sentence on it: “In short, the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems.” The verdict is known well beyond the profession.

The standings

Time to bring the contestants together. In the table below they all sort the same list. Next to our three, two guests compete: heapsort from Chapter 18 and Python’s built-in sorted. The comparisons and moves of our four are counted right in your browser; the comparisons of sorted were counted in advance, in Python itself. And each contestant can show its time on our server at the press of a button. Try every kind of data and every size.

Selection’s count of comparisons never changes, whatever you do. On nearly sorted data insertion beats everyone, heapsort included: it needs only a little more than $n$ comparisons. On shuffled data it makes half as many comparisons as selection, and on reversed data the same number. Bubble sort makes as many moves as insertion but pays more for each, and on shuffled data it loses to everyone on time. Heapsort works in $n \log n$ on any input, and at ten thousand items that puts it in another league. And sorted outruns them all, partly because it is written in C, but mostly because it needs tens or hundreds of times fewer comparisons than the quadratic sorts.

The last column of the table is about one more property. In Chapter 10 we noticed that sorted doesn’t shuffle records with equal keys. Not every sort can say that. Here is a class list, written in alphabetical order, sorted by grade.

After selection, Cora ends up ahead of Ann, although their grades are equal and Ann comes first in the alphabet. The very first swap is to blame: selection put the lowest grade, Dan’s 3, in Ann’s place and sent Ann to the back, over Cora’s head. A sort that keeps the relative order of equal items is called stable. The technique from Chapter 10 relies on stability: sort by the secondary key first, then by the main one, and you get an order by both keys at once. With selection the technique fails. Insertion and bubble sort are stable as long as they move an item only past a strictly bigger neighbor. Change > to >= in them, and the list still comes out sorted, but equal items start trading places.

The prize: twenty questions

We put things in order mostly so that we can search them. In an unordered list a number can be found only by brute force: check the items one by one until the right one turns up. This is linear search; it is how x in some_list works, and in Chapter 13 we watched its time grow with the length of the list. In a sorted list, though, you can play the twenty questions of Chapter 0: compare the target with the middle and throw away the half where it can’t be. This is binary search. A million items take twenty comparisons, a billion take thirty.

The description fits in one sentence and the code in a dozen lines, and yet that code is one of the most famous traps in programming.

Bentley asked his readers to put the book down and try it themselves first. Do try. The cell below holds a plausible first attempt and a strict judge. The judge goes through hundreds of small lists, with repeats and without, and searches them for everything: numbers that are there, numbers that aren’t, numbers smaller than all of them and larger than all of them. Run it, find the bug, fix it and run it again.

The bug is in one line: lo = mid. When one item is left in the range, mid equals lo, and if the target is greater than a[mid], the range stops shrinking and the loop spins forever. The fix is lo = mid + 1: the item a[mid] has already been checked and has no business staying in the range. The judge found the bug by trying cases. But is there a way to know in advance, without guessing, that every line is right?

The invariant

In binary search every line looks obvious, and the bugs hide at the boundaries: < or <=, mid or mid + 1, len(a) or len(a) - 1. To stop guessing, programmers state a loop invariant, a claim that is true before the first iteration and stays true after each one. For our search it is this: if x is in the list, it lies in the slice a[lo:hi]. The slice is half-open, like range: lo is in it, hi is not. Four things remain to be checked.

1. The invariant holds at the start. lo = 0, hi = len(a): the slice is the whole list.
2. Each step keeps it. If a[mid] < x, then in a sorted list everything to the left of mid, and mid itself, is less than x as well; so x can only be in a[mid + 1:hi], and lo = mid + 1 loses nothing. If a[mid] > x, then x can only be in a[lo:mid], and hi = mid is right.
3. The exit gives the answer. The loop ends when lo == hi: the slice is empty, and by the invariant x is not in the list.
4. The loop ends. While lo < hi, the middle satisfies lo <= mid < hi, so both mid + 1 and mid make the slice strictly shorter.

The buggy version broke the fourth point: with mid == lo, lo = mid changes nothing. It kept the other three, which is why its answers were right whenever the loop did end. Other typical bugs are collected in the machine below, each with a broken point of its own.

The first one not less than x

The machine runs the closest relative of binary search, and in practice it is the more useful of the two. The question “is x there, and where?” comes up less often than another one: where in a sorted list do the items not less than x begin? The answer gives you the place to insert x without breaking the order, the number of items less than x, and the start of all the words beginning with “war” in a dictionary. In C++ this function is called lower_bound, in Python bisect_left. Its invariant speaks about both parts of the list at once.

There isn’t a single test for equality here. Each comparison puts an item on one side or the other, “less than x” or “not less than x,” and the loop moves the boundary between them until the unknown middle is gone. Repeats do no harm: for x = 8 the answer is the first of the three eights. And ordinary binary search follows from lower_bound in one line: find the boundary and check whether x stands on it. There are at most $\lceil \log_2 (n + 1) \rceil$ iterations, since the slice gets at least twice as short each time.

In Python all this is already written, in the module bisect: bisect_left is our lower_bound, bisect_right finds the first item strictly greater than x, and insort is the order-keeping insertion we used in Chapter 17. Since version 3.10 they accept a key, like sorted. Here is a search in the dictionary of War and Peace, every different word of the novel in alphabetical order:

The dictionary holds 20,478 words, and each of the two searches asked at most fifteen questions: fifteen halvings bring 20,478 words down to one. A dictionary three times the size would cost one question more, since $2^{16} = 65\,536$. The bound “was” works because in the alphabet “s” comes right after “r”, so everything that starts with “war” lies before “was”. The last four words are a side effect of how we cut the text into words. The Maudes’ translation sets its dashes without spaces, so to our function “war—a” is a single word, as we saw in Chapter 8, and “war’s” keeps its curly apostrophe. Both characters have larger codes than any letter, which is why these words come after “wary”. A database answers the query “all records from here to there” the same way, with two binary searches; we will come back to that in Chapter 46.

What is wrong with taking the average? In Java an int has 32 bits, and its largest value is $2^{31} - 1 = 2\,147\,483\,647$. If an array has more than a billion elements, the sum of two indices may not fit, and you get an overflow, as in Chapter 11: the sum wraps around to a negative number, and the “middle” lands outside the array. We can repeat this in numpy, whose integers behave like Java’s. At least numpy warns about the overflow; Java said nothing.

The bug shows up only on arrays of $2^{30}$ elements or more, a billion and up. When Programming Pearls was written, nobody had arrays like that; by 2006, Bloch wrote, they had become common at Google and elsewhere. The fix is low + (high - low) / 2: the difference of two indices always fits. Python’s integers don’t overflow, so the bug can’t be reproduced in Python. Bloch’s lesson holds for any language: Bentley’s proof was correct, but it rested on an assumption nobody had thought about, that the sum of two indices fits in a 32-bit integer. Bloch’s conclusion: “It is not sufficient merely to prove a program correct; you have to test it too.”

The judge: nobody goes faster

Back to the ring. Every contestant, you included, played by one rule: we learn about the data only through comparisons: “less or not?” Such algorithms are called comparison sorts. How many comparisons do they need? To answer for all of them at once, including those not yet invented, we draw any such algorithm as a tree of questions.

Take three cards, $a$, $b$ and $c$. The algorithm starts with some comparison, say “$a < b$?” What it asks next depends on the answer, so there are two branches. Each holds the next question and two more branches, and so on until the algorithm stops and hands back an order. This is a decision tree: questions in the internal nodes, answers in the leaves. Every input follows its own path through the tree from the root to a leaf, and the number of comparisons on that input is the length of the path.

Insertion has six leaves, one for each of the $3! = 6$ orders, and its longest path is three questions. Selection has eight leaves, and two of them are crossed out: selection sometimes asks something that follows from earlier answers, and one of its branches is never used. Bubble sort with its flag has seven leaves with one crossed out, for the same reason. None of them can get by with fewer than three questions in the worst case, and the reason is the same for all.

This is the argument of twenty questions again: to pick one of $N$ possibilities with yes-or-no answers you need $\lceil \log_2 N \rceil$ questions (in “Mathematics, the Queen of the Sciences” that is the measure of information). For sorting there are $n!$ possibilities. For five cards $\lceil \log_2 120 \rceil = 7$, which is where the seven of round one came from. How fast does $\log_2 n!$ grow? Write out the factorial:

$$\log_2 n! = \log_2 1 + \log_2 2 + \ldots + \log_2 n.$$

Each term is at most $\log_2 n$, so the whole sum is at most $n \log_2 n$. On the other hand, the last $n/2$ terms, from $\log_2 \frac{n}{2}$ to $\log_2 n$, are each at least $\log_2 \frac{n}{2}$, and they alone add up to at least $\frac{n}{2} \log_2 \frac{n}{2}$. Both estimates grow like $n \log n$, so $\log_2 n! = \Theta(n \log n)$. Stirling’s formula pins the number down: $\log_2 n! \approx n \log_2 n - 1.44\, n$. How close does sorted come to the judge’s bound? To count its comparisons, we hand it numbers in a wrapper that counts the calls of <. The special method __lt__ is the one Python calls for a < b, as in Chapter 12.

On a hundred thousand random numbers sorted makes about one percent more comparisons than the bound allows. Selection would make five billion on the same hundred thousand. That is why the dashed “limit” line in the standings sits so close to the bar of sorted.

Go back to the cards of round one and switch to the cunning judge. The cunning judge doesn’t decide on the numbers in advance. He answers each question so as to cross out as few orders as possible: of the two answers he picks the one that leaves more orders standing. At best a question halves what is left, and this judge never grants you the best case. Against him no strategy gets by with fewer than seven questions on five cards. A game against the cunning judge is the theorem itself, played out with cards. Such a judge is called an adversary, and proofs “by adversary” turn up in the theory of algorithms all the time.

The same argument gives a bound for searching. lower_bound on a list of $n$ items has $n + 1$ possible answers, from $0$ to $n$, so it needs at least $\lceil \log_2 (n + 1) \rceil$ comparisons. Binary search makes that many and no more, and twenty questions for a million numbers can’t be improved on.

Out of competition: no comparisons

The judge proved a theorem about those who compare. But nobody is obliged to keep the rule “learn about the data only by comparing.” Suppose you have to sort the test scores of a million students, whole numbers from 0 to 100. There is no need to compare anything: set up 101 counters, go through the list counting how many times each score occurs, then write the scores out in order: so many zeros, so many ones, and so on. This is counting sort, and it takes on the order of $n + k$ steps, where $k$ is the number of possible values.

Counting sort written in Python beats sorted written in C. Why doesn’t the judge’s bound apply? A comparison answers “yes” or “no”: it yields one bit of information. The line counts[s] += 1, on the other hand, sends a score straight into one of 101 cells, which answers a question with a hundred and one possible answers. The $n \log n$ bound is about a game where only yes-or-no questions are allowed; counting sort plays a different game.

Counting works when there are few values. Ten-digit phone numbers can’t be sorted this way: you would need ten billion counters. Help comes from a method used to sort punched cards long before computers: one digit at a time.

Why start with the last digit and not the first? Try it yourself on the machine below, and break it in two ways.

This is radix sort. Why it works is clear from the invariant: after $k$ passes the deck is ordered by its last $k$ digits. Before the first pass this holds: by zero digits everything is in order. Suppose that after $k$ passes the deck is ordered by its last $k$ digits, and we distribute it by the $(k+1)$th digit from the end. Two cards with different $(k+1)$th digits go into different pockets and come out in the right order. Two cards with the same $(k+1)$th digit go into the same pocket, and this is where stability is needed: inside the pocket they must keep the order the earlier passes gave them. Collect a pocket from the bottom up, and the invariant breaks. And if you start from the leading digit, the last pass shuffles everything by the units.

The number of passes equals the number of digits, and each pass is $n$ cards dropped into ten pockets. The base doesn’t have to be ten: in base 256 a digit is a byte, and a 32-bit number has four digits. So Schmidt’s question does have a good answer: a million 32-bit numbers can be sorted in four passes of radix sort by bytes, four million drops into pockets and not one comparison. The price is a demand on the keys: they must split into digits, as numbers, strings and dates do. Sorting students “by height, and by name when the heights are equal” this way is still possible; sorting objects with an arbitrary comparison rule is not.

The champion: Timsort

The tournament was won by the built-in sorted. Its algorithm is called Timsort, after its author. In 2002 Tim Peters, one of Python’s core developers and the author of “The Zen of Python,” replaced the old list sort with it: since version 2.3, Python lists have been sorted by Timsort. A few years later Joshua Bloch, the author of the note on overflow, ported it to Java: since Java 7 it sorts arrays of objects, and Android sorts with it too.

Peters started from an observation: the data programs get in everyday work is rarely random. A list of orders is sorted by time, and a dozen new ones were appended to it; a table was exported sorted by one field and is now being sorted by a neighboring one that almost matches. Such data contains runs, stretches that already go in increasing order (or in strictly decreasing order, and those Timsort reverses). Timsort finds the runs in a single pass. Short runs it lengthens to 32–64 items with the insertion of round three, finding the place for each card by binary search: on short stretches the shifts are cheap. Then it merges the runs in pairs, like two decks of cards, taking care that the pieces it merges are close in length. Merging is the subject of the next chapter. The cell below counts its comparisons on data in various states of readiness.

On a sorted list and on a reversed one, a mere $n - 1$ comparisons: the whole deck is a single run. On a nearly sorted list, a little more than $n$; on a random one, about one percent over the bound. There is no contradiction with the judge: the bound is about the worst case, and a sorted list is Timsort’s best. It spends no comparisons on work that has already been done. And it is stable, so the key techniques of Chapter 10 work with it.

Tasks

Four tasks. Two are about searching, where the boundaries decide everything, and two are about sorting. The built-in sorted, .sort() and the module bisect are off limits in them, and the tests check that.

Write a function binary_search(a, x): a is sorted in non-decreasing order, and the function returns an index at which x stands (if x occurs several times, any of them will do), or -1 if x isn’t there. The tests check every boundary this chapter talked about, and one thing more: the “list” may turn out to be very long, a sequence of $10^{18}$ numbers, say, that are computed from the index and stored nowhere. The function must find the answer in a few dozen reads of a[i]. Another test runs a hundred thousand searches in a million numbers within three seconds. The module bisect and the method .index are banned here.

Take lower_bound from the chapter: it finds the first index i where a[i] >= x. What remains is to check that the item at that index is x.

Careful at the end: if every item is less than x, the boundary equals len(a), and reading a[len(a)] fails. Check the index first, then the value. And don’t use x in a: on $10^{18}$ items the scan would never end.

The order of the checks in the last if matters: and won’t evaluate a[lo] if lo < len(a) is false. On a sequence of $10^{18}$ items the loop makes 60 iterations: $2^{60} \approx 1.15 \cdot 10^{18}$.

A weather station has recorded temperatures over many years, and the list is sorted. Write count_in_range(a, low, high): how many items of the sorted list a lie between low and high inclusive. If low > high, the answer is zero. For example, in the list [-3, 0, 2, 2, 5, 7, 7, 7, 10] six numbers lie between 1 and 7. The function is called 200,000 times on a list of a million numbers, with four seconds for all of it, so going through the list won’t do.

The answer is the difference of two boundaries: where the items not less than low begin, and where the items strictly greater than high begin.

The second boundary is upper_bound: the first index where a[i] > x. It differs from lower_bound by one sign in the condition. Which sign, and why, the invariant will tell you: “everything in a[:lo] is at most x, everything in a[hi:] is greater than x.” The catch lies in repeats at the ends of the range.

If you take lower_bound(a, high) instead of upper_bound(a, high), you lose every item equal to high, and the tests with repeats at the ends catch that. In the module bisect these two functions are called bisect_left and bisect_right.

Write insertion_sort(a, key=None), which sorts the list a in place by insertion sort and returns nothing. If key is given, compare key(x), as sorted does. The sort must be stable. And the tests will slip in a nearly sorted list of two hundred thousand items: insertion has to get through it within a second, since that is where its strength lies.

If key isn’t given, the key “the value itself” will do: key = lambda x: x. Compute the new card’s key once, before the inner loop.

Stability and speed on nearly sorted data come from the same thing: move an item left only past neighbors with a strictly greater key, and stop as soon as you meet one that isn’t greater.

On a nearly sorted list the inner loop stops almost at once, and the whole job comes to about $n$ comparisons plus one shift per inversion. Selection would make twenty billion comparisons on the same data. The neighbor’s key key(a[j]) is computed afresh at every step here; if the key is expensive, it can be computed in advance for every item, which is what sorted does.

Write radix_sort(a), which returns a new list with the nonnegative integers from a in increasing order. You may not compare the items with each other, only drop them into pockets, like Hollerith’s machine, from the lowest digit to the highest. The numbers vary in length, from zero to $10^{18}$. A hundred thousand numbers must be sorted in four seconds.

One pass: make ten empty lists for pockets, put each number into the pocket of its digit (x // place) % 10, where place is 1, 10, 100…, and collect the pockets from zero to nine.

How many passes? Until place exceeds the largest number: by then every digit of the longest number has been used, and the shorter numbers have zeros for their leading digits. The function max will find the largest number; it doesn’t count as sorting. Don’t forget the empty list.

Stability comes free here: append puts the numbers into a pocket in the order they arrive, and collecting lays each pocket out from start to end. The time is the number of digits of the largest number times $n$. For numbers up to $10^{18}$ that makes nineteen passes; in base 256, eight would do.

What next

Selection, insertion and bubble sort are clear at first sight, but all three are quadratic: on shuffled data their work grows like $n^2$. A fast processor and careful code won’t help: binary search for the insertion point only moves the square from the comparisons to the shifts, and bubble sort’s flag helps only on nearly sorted data. On a billion numbers the square means on the order of $10^{18}$ comparisons (selection makes $n^2/2 = 5 \cdot 10^{17}$), years of work. The floor the judge found lies far lower, at $n \log n$, and heapsort from Chapter 18 and the champion Timsort reach it. But a heap is a clever device built for one job, and Timsort’s heart, merging, we have only glimpsed so far. We need a general idea that gives $n \log n$ by construction and is good for more than sorting. In the next chapter it arrives with two people who turned up at Moscow University at almost the same time.