Divide and conquer

Every quadratic sort is stuck because it removes disorder one inversion at a time, so beating it needs an algorithm with a different shape entirely.

The shape

Divide and conquer is a three-step pattern. Divide the problem into smaller instances of the same problem. Conquer them by solving each recursively, stopping at a base case small enough to solve outright. Combine the sub-answers into an answer for the whole.

Binary search is already an instance, in a degenerate way: it divides into two halves, conquers one of them, and needs no combination step at all. What makes the pattern powerful is the case where both halves are solved and the combination is cheap, because then the work at each level of recursion is proportional to the data at that level, and the number of levels is logarithmic.

The reason this can beat $Θ (n^{2})$ is precisely the thing insertion sort could not do. When two sorted halves are merged, a single comparison between the fronts of the two halves can settle the relative order of one element against every remaining element of the other half at once. Each comparison carries more information than a comparison of neighbours, because the sortedness of the halves is being used.

Recurrences

A divide-and-conquer algorithm's cost is naturally written as an equation in terms of itself. If splitting into $a$ subproblems of size $n / b$ costs $f (n)$ for the dividing and combining, the total is

T (n) = a T (n / b) + f (n)

with a base case such as $T (1) = Θ (1)$ . This is a recurrence, and solving it means finding a closed form for $T (n)$ .

The first method is the recursion tree, and it is the one to reach for because it shows why the answer is what it is. Draw the root as the top-level call, costing $f (n)$ . It has $a$ children each costing $f (n / b)$ , each of which has $a$ children costing $f (n / b^{2})$ , and so on until the subproblem size reaches 1, which happens at depth $\log_{b} n$ . Sum the cost of each level, then sum the levels.

Take mergesort's recurrence, $T (n) = 2 T (n / 2) + n$ . The root costs $n$ . Level 1 has two nodes costing $n / 2$ each, total $n$ . Level 2 has four nodes costing $n / 4$ each, total $n$ . Every level costs exactly $n$ , and there are $\log_{2} n + 1$ of them, so

T (n) = n (\log_{2} n + 1) = Θ (n \log n)

The shape of the answer is visible in the drawing: the work per level is constant, so the total is work-per-level times number-of-levels.

Three other shapes occur. If the per-level total shrinks geometrically going down, as in $T (n) = 2 T (n / 2) + n^{2}$ , where levels cost $n^{2}$ , $n^{2} / 2$ , $n^{2} / 4$ , the sum is dominated by the root and $T (n) = Θ (n^{2})$ . If it grows geometrically, as in $T (n) = 4 T (n / 2) + n$ , where levels cost $n$ , $2 n$ , $4 n$ , the sum is dominated by the leaves. If it stays level, as in mergesort, the logarithm appears.

Example. Solve $T (n) = 2 T (n / 2) + Θ (1)$ by recursion tree, and say which algorithm it describes.

Level 0 costs 1, level 1 costs 2, level 2 costs 4, and level $k$ costs $2^{k}$ . At depth $\log_{2} n$ there are $n$ leaves, and the sum $1 + 2 + 4 + \dots + n = 2 n - 1$ is dominated by the last level. So $T (n) = Θ (n)$ . This describes an algorithm that splits in two, recurses on both halves, and does constant work to combine: for instance finding the maximum of an array by halving, which does $n - 1$ comparisons in total, the same as the obvious loop.

Now you. Solve $T (n) = T (n / 2) + Θ (1)$ , and name the algorithm.

Answer

Each level has exactly one node costing a constant, and there are $\log_{2} n + 1$ levels, so $T (n) = Θ (\log n)$ . That is binary search: one subproblem of half the size, constant work to pick the midpoint and compare.

The master theorem

The recursion tree generalises into a formula, and the formula is worth having because most recurrences that arise in practice are of exactly this form. For $T (n) = a T (n / b) + f (n)$ with $a \geq 1$ and $b > 1$ , compare $f (n)$ against the quantity $n^{\log_{b} a}$ , which is the total cost of the leaves.

If $f (n) = O (n^{\log_{b} a - ε})$ for some $ε > 0$ , the leaves dominate and $T (n) = Θ (n^{\log_{b} a})$ .

If $f (n) = Θ (n^{\log_{b} a})$ , every level costs about the same and $T (n) = Θ (n^{\log_{b} a} \log n)$ .

If $f (n) = Ω (n^{\log_{b} a + ε})$ for some $ε > 0$ , and additionally $a f (n / b) \leq c f (n)$ for some $c < 1$ and all large $n$ , the root dominates and $T (n) = Θ (f (n))$ .

Applied: mergesort has $a = 2$ , $b = 2$ , so $n^{\log_{2} 2} = n$ , and $f (n) = n$ matches, giving case two and $Θ (n \log n)$ . Binary search has $a = 1$ , $b = 2$ , so $n^{\log_{2} 1} = n^{0} = 1$ , and $f (n) = 1$ matches, giving $Θ (\log n)$ . The obvious matrix multiplication algorithm splits each matrix into four blocks and does eight block multiplications plus $Θ (n^{2})$ additions: $a = 8$ , $b = 2$ , $n^{\log_{2} 8} = n^{3}$ dominates $n^{2}$ , so case one gives $Θ (n^{3})$ , agreeing with the triple loop. Strassen's trick does seven block multiplications instead of eight, so $n^{\log_{2} 7} = n^{2.807}$ , which is where that exponent comes from.

The theorem has gaps, and pretending otherwise causes errors. It says nothing when $f (n)$ falls between two cases: $T (n) = 2 T (n / 2) + n \log n$ has $n^{\log_{b} a} = n$ , and $n \log n$ is bigger than $n$ but not by a factor of $n^{ε}$ , so no case applies. (A recursion tree settles it: $Θ (n \log^{2} n)$ .) It also assumes all subproblems have the same size, which quicksort's do not, so the next lesson needs a different method entirely.

Mergesort

Now build the sort. To sort $n$ elements: if $n \leq 1$ it is already sorted; otherwise split the array in half, sort each half recursively, and merge the two sorted halves into one sorted whole.

The merge is the only part with content. Keep an index into each sorted half. Compare the two elements they point at, copy the smaller into the output, and advance that index. When one half is exhausted, copy the rest of the other. Every comparison consumes one element, so merging two runs of total length $m$ costs at most $m - 1$ comparisons and exactly $m$ moves.

Correctness of the merge is the loop invariant that the output holds, in sorted order, exactly the elements already consumed from both inputs, and that every unconsumed element is at least as large as every consumed one. That second clause is what the sortedness of the halves buys, and it is why the smaller of the two front elements is safe to emit.

The cost recurrence is $T (n) = 2 T (n / 2) + Θ (n)$ , so $T (n) = Θ (n \log n)$ by the tree above, and this is a worst-case bound: no input makes mergesort slow, because the split does not look at the data. Counting comparisons exactly for $n$ a power of two gives a worst case of $n \log_{2} n - n + 1$ , which is 17 for $n = 8$ , 49 for $n = 16$ , and about 18.9 million for a million elements. The best case, on input where every merge exhausts one side first, is $(n \log_{2} n) / 2$ , so the spread between best and worst is only a factor of two.

Mergesort is stable if the merge prefers the left run on ties, and that is the standard implementation. Its cost is memory: the merge cannot be done in place without either extra space or a much more complicated algorithm, so the usual version allocates a second array of size $n$ . In-place merging exists but the known methods are slow enough in constant factors that libraries prefer paying the memory.

Example. Merge the sorted runs 2, 5, 8, 13 and 1, 3, 9, 11. How many comparisons does it take, and what is the fewest a merge of two four-element runs could take?

Comparing fronts: 2 against 1 emits 1; 2 against 3 emits 2; 5 against 3 emits 3; 5 against 9 emits 5; 8 against 9 emits 8; 13 against 9 emits 9; 13 against 11 emits 11; and the left run's 13 is copied without a comparison. Seven comparisons, which is the maximum $m - 1 = 8 - 1$ . The minimum is four, achieved when one run is entirely smaller than the other, as with 1, 2, 3, 4 and 5, 6, 7, 8: four comparisons exhaust the left run and the right is copied wholesale.

Now you. How many comparisons does mergesort make in the worst case on 16 elements, and how many on a million?

Answer

Using $n \log_{2} n - n + 1$ : for $n = 16$ that is $16 \times 4 - 16 + 1 = 49$ . For $n = 10^{6}$ it is $10^{6} \times 19.93 - 10^{6} + 1 \approx 1.89 \times 10^{7}$ , about 18.9 million. A quadratic sort on the same million elements would use 500 billion, a factor of 26,000.

The same idea elsewhere

Divide and conquer is not a sorting technique, and the clearest evidence is a problem with no order in it at all.

Multiplying two $n$ -digit numbers by the method taught in school costs $Θ (n^{2})$ digit multiplications. In 1960 Andrey Kolmogorov conjectured in a seminar that $Θ (n^{2})$ was optimal; within a week the 23-year-old Anatoly Karatsuba had refuted him.

Split each number into halves: $x = a \cdot 10^{m} + b$ and $y = c \cdot 10^{m} + d$ with $m = n / 2$ . Then

x y = a c \cdot 10^{2 m} + (a d + b c) \cdot 10^{m} + b d

which needs four half-size multiplications: $a c$ , $a d$ , $b c$ , $b d$ . That gives $T (n) = 4 T (n / 2) + Θ (n)$ , and $n^{\log_{2} 4} = n^{2}$ , so case one of the master theorem returns $Θ (n^{2})$ : no gain, which is expected, since this is the school method rearranged.

Karatsuba's observation is that the middle term can be had for one multiplication rather than two, because

(a + b) (c + d) = a c + a d + b c + b d

so $a d + b c = (a + b) (c + d) - a c - b d$ , and $a c$ and $b d$ are already being computed. Three half-size multiplications suffice, with some extra additions, giving $T (n) = 3 T (n / 2) + Θ (n)$ and $T (n) = Θ (n^{\log_{2} 3}) = Θ (n^{1.585})$ .

Example. Multiply $1234 \times 5678$ by Karatsuba, splitting each into two-digit halves.

Here $a = 12$ , $b = 34$ , $c = 56$ , $d = 78$ , and $m = 2$ . The three products are $a c = 12 \times 56 = 672$ , $b d = 34 \times 78 = 2652$ , and $(a + b) (c + d) = 46 \times 134 = 6164$ . The middle term is $6164 - 672 - 2652 = 2840$ . Assembling, $672 \times 10^{4} + 2840 \times 10^{2} + 2652 = 6 {,} 720 {,} 000 + 284 {,} 000 + 2652 = 7 {,} 006 {,} 652$ , which is the right answer, using three two-digit multiplications instead of four.

Now you. Multiply $3141 \times 2718$ the same way.

Answer

$a = 31$ , $b = 41$ , $c = 27$ , $d = 18$ . Then $a c = 837$ , $b d = 738$ , and $(a + b) (c + d) = 72 \times 45 = 3240$ , so the middle term is $3240 - 837 - 738 = 1665$ . Assembling: $837 \times 10^{4} + 1665 \times 10^{2} + 738 = 8 {,} 370 {,} 000 + 166 {,} 500 + 738 = 8 {,} 537 {,} 238$ .

Be honest about the size at which this pays. The extra additions and the recursion overhead mean Karatsuba loses to the school method on small numbers, and library implementations such as GMP switch over somewhere around 300 to 2500 bits depending on the machine. At 4096 bits, the size of a large RSA key, the asymptotic gap is a factor of about 32, and there it is decisive.

What mergesort still costs

Mergesort delivers a guaranteed $Θ (n \log n)$ and stability, and it charges $Θ (n)$ extra memory for them. For a million records that is another eight megabytes, which is usually irrelevant; for sorting a large fraction of available memory, or on an embedded device, it is not.

The next lesson takes the opposite trade. It partitions the array in place, spending no extra memory beyond the recursion stack, and it is measurably faster than mergesort on real hardware because it moves data less and touches memory more sequentially. What it gives up is the guarantee: its worst case is quadratic, and the reason that rarely matters is a probability argument rather than a proof about the algorithm alone.