ALGO·III Algorithms Chapter 21 of 65
Divide and conquer
Two Moscow stories: a graduate student who proved Kolmogorov wrong within a week, and an English visitor who had to sort Russian words for a machine translator. Both cut their problem in half, and the algorithms inside every computer rest on that move.
Algorithms
- 20 Search and sort
- 21 Divide and conquer you are here
- 22 Dynamic programming
- 23 Greedy
- 24 Shortest paths
- 25 Flows, matchings
- 26 Randomness
- 27 Text search
Builds on: 20 · The sorting tournament 09 · A problem inside a problem
What you will take away
- recognize problems that give way when cut in half, and write the recursion for them
- work out running time with a recursion tree and the master theorem
- why quicksort is quick, and when it turns slow
The last chapter ended at a dead end. Insertion sort and selection sort make on the order of $n^2$ comparisons, and neither a faster processor nor tidier code will change that: on a billion numbers the square comes to about $10^{18}$ comparisons, years of work. We need another idea. It came from two people who found themselves at Moscow State University at almost the same time and, without comparing notes, hit on the same move.
Moscow, 1960. Kolmogorov’s conjecture
The school method is indeed quadratic: each digit of the top number is multiplied by each digit of the bottom one, which fills an $n \times n$ table. Two-digit numbers take four digit products, ten-digit numbers a hundred, thousand-digit numbers a million.
Three products instead of four
Karatsuba began by cutting each number in half. Take the four-digit $x = 1234$ and $y = 5678$. They can be written as $x = 12 \cdot 100 + 34$ and $y = 56 \cdot 100 + 78$. In general, if the numbers have $n$ digits and $B = 10^{n/2}$,
$$x = a \cdot B + b, \qquad y = c \cdot B + d.$$Multiply them out:
$$x \cdot y = ac \cdot B^2 + (ad + bc) \cdot B + bd.$$Multiplying by $B$ only appends zeros, so it isn’t worth counting. That leaves four products of halves: $ac$, $ad$, $bc$, $bd$. Computing them the same way, recursively, gains nothing: four problems of half the size add up to $n^2$ again (we will count why below). But Karatsuba saw that the middle coefficient can be had without computing $ad$ and $bc$ separately:
$$ad + bc = (a + b)(c + d) - ac - bd.$$
Multiply out the right-hand side: $(a + b)(c + d) = ac + ad + bc + bd$. Subtract $ac$ and $bd$, and $ad + bc$ is what remains.
The proof takes one line, and the consequence is large. We need $ac$ and $bd$ anyway, so the middle coefficient costs a single new product, $(a+b)(c+d)$, and the halves get multiplied three times instead of four. In our example $ac = 12 \cdot 56 = 672$, $bd = 34 \cdot 78 = 2652$, $(a+b)(c+d) = 46 \cdot 134 = 6164$, and the middle coefficient is $6164 - 672 - 2652 = 2840$. Altogether $672 \cdot 10^4 + 2840 \cdot 10^2 + 2652 = 7\,006\,652$; check it on a calculator.
One product saved out of four is only a quarter. But the saving repeats on every level of the recursion: each of the three products of halves is itself done with three products of quarters, and so on down to single digits. Run the program and count the digit products.
On 64-digit numbers long multiplication spends 4096 digit products, Karatsuba about a thousand, and the longer the numbers, the wider the gap. The count overshoots $3^6 = 729$ because of carries: the sum $a + b$ is sometimes one digit longer than a half. That extra doesn’t change the rate of growth.
Kolmogorov, as Karatsuba remembered it, “was very agitated because this contradicted his very plausible conjecture.” At the next meeting Kolmogorov himself told the participants about the new method, and with that the seminar came to an end. In 1962 Kolmogorov wrote a short paper on the method, “probably in collaboration with Ofman,” in Karatsuba’s words, and published it in Doklady, the journal of the Soviet Academy of Sciences, under the names of Karatsuba and Yuri Ofman. Karatsuba learned of the paper only when he was handed the reprints.
Divide, solve, combine
Leave multiplication aside for a moment. Karatsuba’s method had three steps:
- Divide the problem into several problems of the same kind, only smaller: the numbers into halves.
- Solve each part the same way, by recursion, until the parts are tiny, a single digit.
- Combine the answers for the parts into the answer for the whole: add them with the right shifts.
This approach is called divide and conquer, after the Latin maxim divide et impera, attributed variously to Julius Caesar and to Machiavelli. It is one of the central ideas of programming. You have met it already in binary search: halve the range, solve the problem in one half, and there is nothing to combine. All that is left is to apply it to sorting, the problem that brought us here.
Merge sort
Suppose you can already sort lists half as long. Then a long list is sorted like this: sort both halves, then merge them. Merging two sorted piles of cards is easy: compare the top cards of both, take the smaller one, repeat. Try it: click the smaller of the two top cards.
Every comparison sends one card to the result, so two piles holding $n$ cards between them merge in at most $n - 1$ comparisons. Merging is our “combine” step, and recursion does the rest: the halves are sorted the same way, and their halves too, until only one-item lists are left, which are sorted already.
Merge sort was described by John von Neumann in 1945, one of the first algorithms for the EDVAC, a machine that was still being designed. Here it is in Python. Press “Steps” to watch the recursion go down and come back up: on the right you will see the frames of the calls, each with its own piece of the list.
What it costs
How many comparisons does merge sort make? Draw all the calls as a tree. At the top is a single call on the whole list of length $n$: it merges two halves, up to $n$ comparisons. Below it are two calls on the halves, each merging up to $n/2$, which makes $n$ again. On the next level four calls of $n/4$ add up to $n$ once more. Every level costs $n$, and there are as many levels as there are halvings from $n$ down to one, that is, $\log_2 n$.
Merge sort puts $n$ items in order with at most $n \log_2 n$ comparisons.
For simplicity let $n$ be a power of two, $n = 2^k$. A call on a list of length $m$ makes at most $m$ comparisons of its own (while merging) plus two calls on lists of length $m/2$. On level $i$ of the call tree (the root is level $0$) there are $2^i$ calls, each on a list of length $n / 2^i$, and together they make at most $2^i \cdot n/2^i = n$ comparisons. The levels whose lists have length 2 or more are $i = 0, 1, \ldots, k-1$, and there are $k = \log_2 n$ of them; the bottom level holds one-item lists and makes no comparisons. The sum over the levels is at most $n \cdot \log_2 n$. If $n$ is not a power of two, the tree is no deeper than $\lceil \log_2 n \rceil$, and the bound becomes $n \lceil \log_2 n \rceil$.
A million numbers means $\log_2 10^6 \approx 20$ levels of a million comparisons each: twenty million, against half a trillion for the quadratic sorts, a factor of twenty-five thousand. In the last chapter we proved that any comparison sort needs at least $\log_2 n! \approx n \log_2 n$ comparisons in the worst case. Merge sort is therefore optimal: in order of growth, nothing can beat it.
The recursion tree and the master theorem
The same tree gives the running time of any divide-and-conquer algorithm. Say a problem of size $n$ splits into $a$ subproblems of size $n/b$, and the dividing and combining cost on the order of $n^d$ operations. Then the running time $T(n)$ obeys a recurrence:
$$T(n) = a \cdot T\!\left(\frac{n}{b}\right) + n^d.$$Merge sort: $a = 2$, $b = 2$, $d = 1$. Karatsuba: $a = 3$, $b = 2$, $d = 1$ (the additions and shifts are linear). Multiplying by halves without the identity: $a = 4$, $b = 2$, $d = 1$. Binary search: $a = 1$, $b = 2$, $d = 0$. Play with the parameters: on which level of the tree does the work pile up?
Level $i$ holds $a^i$ subproblems of size $n/b^i$, each costing $(n/b^i)^d$, together $n^d \cdot \left(\frac{a}{b^d}\right)^i$. The lengths of the bars form a geometric progression, and everything depends on its ratio $q = a / b^d$.
If $T(n) = a\,T(n/b) + n^d$, where $a \ge 1$, $b > 1$, $d \ge 0$, then
- for $a < b^d$ the work shrinks down the tree, and $T(n) = \Theta(n^d)$: most of the time goes to the root;
- for $a = b^d$ every level costs the same, and $T(n) = \Theta(n^d \log n)$;
- for $a > b^d$ the work grows down the tree, and $T(n) = \Theta\!\left(n^{\log_b a}\right)$: most of the time goes to the leaves.
The tree has depth $\log_b n$, and level $i$ does $n^d q^i$ work, where $q = a/b^d$. In total $T(n) = n^d \sum_{i=0}^{\log_b n} q^i$. If $q < 1$, the sum of a decreasing geometric progression, even an infinite one, is at most $\frac{1}{1-q}$, a constant, and $T(n) = \Theta(n^d)$. If $q = 1$, all $\log_b n + 1$ terms equal one, and $T(n) = \Theta(n^d \log n)$. If $q > 1$, the last term decides: $\sum_{i=0}^{L} q^i < \frac{q}{q-1} q^{L}$ for $L = \log_b n$. And $n^d q^{\log_b n} = n^d \cdot \frac{a^{\log_b n}}{n^d} = a^{\log_b n} = n^{\log_b a}$, the number of leaves in the tree. That gives $T(n) = \Theta(n^{\log_b a})$.
This shows why Karatsuba wins. With four products of halves, $a = 4 > 2^1$: the work piles up in the leaves, and there are $n^{\log_2 4} = n^2$ of them, the same square as in long multiplication. With three products there are $n^{\log_2 3} \approx n^{1.585}$ leaves. One product saved on each level becomes a different exponent.
An algorithm splits a problem into 8 subproblems of half the size and spends on the order of $n^2$ operations combining their answers. How does its running time grow?
$a = 8$, $b = 2$, $d = 2$, $b^d = 4 < 8$: the work grows toward the leaves, and the time is $\Theta(n^{\log_2 8}) = \Theta(n^3)$. That is how naive recursive matrix multiplication behaves. In 1969 Volker Strassen did for matrices what Karatsuba had done for numbers: seven block products instead of eight, $n^{\log_2 7} \approx n^{2.81}$.
Moscow, 1959. Tony Hoare and a dictionary on magnetic tape
Merge sort cuts the list mechanically, down the middle, and does all its thinking while combining. Hoare’s method is the other way around: all the thought goes into the cutting, and there is nothing to combine. Pick any item of the list (it is called the pivot) and lay out the others in two piles: those smaller than the pivot on the left, those larger on the right. The pivot goes between them, into its final place. Now sort the piles by the same procedure, and the whole list is sorted, because everything on the left is already smaller than everything on the right.
Laying the items out in piles is called partition, and it takes a single pass: pointers start from both ends and move toward each other, and whenever each one finds an item on the wrong side, the two items swap places. In Python it is easier to build the piles as new lists, and then the algorithm reads almost like its definition:
When quicksort is slow
If the pivot splits the list roughly in half every time, the recursion tree looks like merge sort’s, and the work is $n \log n$. But what if the pivot turns out to be the smallest item? Then one pile is empty and the other holds $n - 1$ items. If that happens time after time, the tree stretches into a pole of depth $n$, and the comparisons add up to $n + (n-1) + \ldots + 1 \approx n^2/2$, as many as bubble sort makes.
That is what happens if you always take the first item as the pivot and feed in a list that is already sorted. The second half of the program ends in an error, as intended.
On a sorted list the recursion has to go five thousand levels deep, and Python stops it at about a thousand: it limits the depth of calls. Even without that limit the sort would take quadratic time. The defense is easy: choose the pivot at random, as in the first version. Then no input is bad every time; only unlucky coin tosses are, and they are rare. On average, random quicksort makes about $1.39\, n \log_2 n$ comparisons, and Chapter 26 works out why.
Hoare published quicksort in 1961, and it has been one of the most widely used programs in the world ever since: variants of it run in the standard libraries of C++ and Java. Hoare received the Turing Award in 1980 for his contributions to the definition and design of programming languages; he died in March 2026, at the age of 92. In Chapter 53 we will meet him again, confessing to his “billion-dollar mistake.”
What Python itself does
Merge sort and Karatsuba’s method are at work on your computer right now. Python’s sorted uses Timsort, a hybrid of merge sort and insertion sort that Tim Peters wrote for Python in 2002. And CPython multiplies integers by Karatsuba’s method once they get long. The clock shows it: doubling the length of the numbers should make the multiplication about $2^{1.58} \approx 3$ times slower, not 4.
Each doubling takes about three times as long. The refutation of Kolmogorov’s conjecture is built into CPython, and our server has just made use of it.
Tasks
Four tasks, from a warm-up to an interview classic. All of them are tested on large inputs with a time limit, so a quadratic solution won’t pass.
Write a function merge_sort(a) that returns a new list with the items of a in increasing order. The built-in sorted and .sort() are off limits, and the tests will check. On a list of 200,000 numbers the function should finish in a couple of seconds.
Start with a function merge(left, right) that merges two sorted lists with two pointers. At the end, don’t forget to add the tail left over in one of the lists.
The recursion: merge(merge_sort(a[:mid]), merge_sort(a[mid:])), where mid = len(a) // 2.
The <= in the comparison makes the sort stable: equal items keep their relative order. That matters when records are sorted by one field after another, say first by name and then by city: within each city the names stay in alphabetical order.
Write a function kth_smallest(a, k) that returns the $k$-th smallest item of a list (for $k = 1$ the minimum, for $k = $ len(a) the maximum). There is no need to sort the whole list: think about how Hoare’s partition can help. On a million numbers the function should be noticeably faster than sorting.
Partition the list around a random pivot into smaller, equal and larger items. Compare $k$ with the sizes of the piles: which pile holds the answer?
You only have to recurse into one pile, not both. If the pivot lands near the middle every time, the work is $n + n/2 + n/4 + \ldots \approx 2n$; with a random pivot the time is linear on average too.
Hoare invented this algorithm too; it is called quickselect. It is one way to find a median, for instance.
An inversion in a list is a pair of positions $i < j$ where a[i] > a[j]. A sorted list has no inversions; a reversed one has $n(n-1)/2$. The number of inversions measures how “shuffled” a list is, which is how, for example, two rankings of the same movies can be compared. Write count_inversions(a). Going through all pairs of 100,000 items won’t fit in the time limit.
Sort by merging and count the inversions on the way. Inversions come in three kinds: both positions in the left half, both in the right half, and “across the border.”
When the merge takes an item from the right half, that item is smaller than every item still waiting in the left half, and it forms an inversion with each of them. How many are waiting? len(left) - i.
The time is $n \log n$, as for merge sort: the counting adds one addition to each step of the merge.
Write a function karatsuba(x, y) that multiplies non-negative integers recursively, by Karatsuba’s method. The built-in * is allowed only in the base case, when one of the numbers is less than 10. That rule is on your honor: the tests check only that the answer is right, and the point of the task is the recursion.
Cut both numbers at the same position $m$, half the length of the longer one: a, b = divmod(x, 10 ** m).
The solution is the cell from the beginning of the chapter, minus the counting. In it, B * B and middle * B are multiplications by powers of ten, that is, appending zeros; library implementations use a shift instead.
What next
Divide and conquer has a weak spot. Remember the recursive Fibonacci numbers from Chapter 9: fib(n) calls fib(n-1) and fib(n-2), those call theirs, and the call tree grows exponentially, even though there are only $n + 1$ different subproblems. In sorting, the halves don’t overlap; in Fibonacci, the same subproblems are solved millions of times over. What if we remembered the ones already solved? Then the exponential turns into a straight line, and a whole method stands on that thought: dynamic programming. The man who named it said he chose the name so that the Secretary of Defense wouldn’t guess it was mathematics.