Divide and Conquer & Mergesort

Some problems are easiest to solve by reducing them to smaller versions of themselves. This is the divide-and-conquer paradigm, and it is one of the most productive ideas in all of algorithm design. Every divide-and-conquer algorithm has the same three-part skeleton:

• Divide the problem into one or more subproblems that are smaller instances of the same problem.
• Conquer the subproblems by solving them recursively. When a subproblem is small enough (the base case), solve it directly without recursing.
• Combine the subproblem solutions into a solution for the original problem.

Erickson's advice captures the mindset: assume the recursion already works, so that the recursive calls correctly solve the smaller instances, and focus your energy on the divide and combine steps. This recursion fairy¹ stance turns a single hard problem into two manageable questions: how do I split? and how do I merge?

The payoff is always a recurrence. If an instance of size $n$ spawns $a$ subproblems each of size $n/b$, and the divide-plus-combine work costs $\Theta (n^c)$, then the total cost obeys

Almost every algorithm in this module is an exercise in choosing $a$, $b$, and $c$ wisely and then reading off $T(n)$. The master theorem (stated at the end of this lesson) turns that reading-off into a mechanical three-case rule; the recursion tree is the picture behind it. Mergesort is the cleanest first example, so we start there.

The sorting problem, revisited

Recall the specification from the previous module:

Insertion sort grew a sorted prefix one element at a time, costing $\Theta (n^2)$ in the worst case. Divide and conquer does much better. The trick is to ask: if I already had two sorted halves, could I finish the job cheaply? The answer, yes, by merging, gives us mergesort.²

Mergesort

To sort the subarray $A[p..r]$, split it at the midpoint $q=\lfloor (p+r)/2\rfloor$, recursively sort the two halves, and merge them back together. A single element ($p\ge r$) is already sorted, so it is the base case.

All the real work lives in the combine step. $\text{Merge}$ takes two adjacent sorted runs, $A[p..q]$ and $A[q+\mathrm{1..}r]$, and interleaves them into a single sorted run in place. It copies each half into a scratch array, then repeatedly takes the smaller of the two front elements and writes it back.

The two sentinel values $\infty$ are a small but useful device: once one half is used up, its front element is forever $\infty$, so the comparison always picks from the other half. This removes the need to test have we run out? on every iteration.

Picture the merge in flight. Two sorted runs $L$ and $R$ sit above the output; the cursors $i$ and $j$ point at their smallest uncopied elements, and $k$ marks where the next winner lands in $A$. Each step compares $L[i]$ to $R[j]$, writes the smaller, and advances that one cursor.

Here $L[i]=11$ and $R[j]=8$, so $R[j]$ wins: it is written to $A[k]$ and $j$ advances. The two $\infty$ sentinels guard the right ends so the comparison is always well-defined.

Why merge is correct

Merge runs in $\Theta (n)$ time on $n=r-p+1$ elements: each of the $n$ iterations of the final for loop does $O(1)$ work and advances exactly one of $i$, $j$. Correctness rests on a loop invariant:

• Initialization. Before the first iteration $k=p$, so $A[p..k-1]$ is empty: it holds the $0$ smallest elements, vacuously sorted. Since nothing has been copied, $L[1]$ and $R[1]$ are indeed the smallest uncopied elements.
• Maintenance. Suppose $L[i]\le R[j]$ (the other case is symmetric). Then $L[i]$ is the smallest uncopied element. Appending it to the sorted $A[p..k-1]$ keeps $A[p..k]$ sorted and now containing the $k-p+1$ smallest elements. Incrementing $i$ and $k$ restores the invariant.
• Termination. The loop ends with $k=r+1$, so $A[p..r]$ holds all $r-p+1$ elements in sorted order. The sentinels guarantee we never read past the real data.

Run the loop to completion on the two halves $⟨2,4,5,7⟩$ and $⟨1,2,3,6⟩$ and every element lands in its sorted slot below:

Analyzing the cost

Let $T(n)$ be the worst-case running time of mergesort on $n$ elements. Splitting costs $\Theta (1)$, the two recursive calls cost $2T(n/2)$, and the merge costs $\Theta (n)$. So

To see why this resolves to $\Theta (n\log n)$, draw the recursion tree. Each node is labeled with the non-recursive work it does, the cost of its own merge. The root merges $n$ elements; its two children each merge $n/2$; the next level has four nodes each merging $n/4$; and so on.

The key observation: each level sums to the same amount. The root level is $cn$; the next is $2\cdot cn/2=cn$; the next is $4\cdot cn/4=cn$; in general level $i$ has $2^i$ nodes each doing $cn/2^i$ work, for a row total of $cn$.

Halving from $n$ down to the base case of $1$ takes ${\log }_{2}n$ steps, so there are ${\log }_{2}n+1$ levels. Multiplying the per-level cost by the number of levels:

This is the canonical application of the master theorem ($a=2$, $b=2$, $f(n)=\Theta (n)$, so $n^{{\log }_{b}a}=n$ and we land in the balanced case), but the recursion tree makes the $n\log n$ concrete: $\log n$ levels, $n$ work apiece.

Stability

Mergesort is stable: equal elements keep their original relative order. This falls out of the $\le$ in $\text{Merge}$: when $L[i]=R[j]$ we take from $L$, the left (earlier) half, first. Stability matters when records are sorted on one key but carry others: a stable sort lets you sort by secondary key, then primary key, and trust that ties on the primary preserve the secondary ordering.

Mergesort versus other sorts

Mergesort's worst-case guarantee and stability make it the sort of choice when predictability matters or when data does not fit in memory. Its sequential, merge-based access pattern is ideal for sorting linked lists and for external sorting of data streamed from disk.³ Its cost is the $\Theta (n)$ auxiliary array. Quicksort, the subject of the next lesson, trades that guarantee for better constants and in-place operation.

Counting inversions

Here is a problem that has nothing to do with sorting on its surface, yet falls to the very machinery we just built. Given a list $⟨a_1,a_2,\dots ,a_n⟩$, how close to sorted is it? A natural measure counts the pairs that are out of order.

A sorted array has zero inversions; a reverse-sorted one has the maximum, $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$. (Inversion counts also drive collaborative-filtering how similar are two rankings? scores.) The brute-force algorithm loops over all pairs and counts the bad ones, costing exactly $\left(\genfrac{}{}{0ex}{}{n}{2}\right)=\frac{1}{2}n(n-1)=\Theta (n^2)$ comparisons. We can do far better.

Idea 0: divide and conquer, just like mergesort. Split $A$ into a left half $B$ and a right half $C$. Every inversion is one of three kinds:

• both endpoints in $B$, counted by recursing on $B$;
• both endpoints in $C$, counted by recursing on $C$;
• one endpoint in each: a cross inversion, $i$ on the left and $j$ on the right with $B[i]>C[j]$.

Counting cross inversions with a double loop costs $\Theta (n^2)$ for the combine step, giving $T(n)=2T(n/2)+\Theta (n^2)$, which the master theorem resolves to $\Theta (n^2)$, no gain. The combine step is the bottleneck.

Idea 1: count cross inversions during a merge. Suppose the two halves arrive already sorted. Walk them with two cursors exactly as $\text{Merge}$ does. When we are about to emit and $B[i]>C[j]$, the element $C[j]$ is smaller than $B[i]$ and than everything after it in $B$, so $C[j]$ forms an inversion with all $p-i+1$ remaining elements of $B$ at once. Add that count, emit $C[j]$, and move on.

This batching is exactly why the count collapses to linear time: a single comparison reveals $p-i+1$ inversions, not one. Because $B$ is sorted, every element from $B[i]$ onward exceeds $C[j]$, so each is inverted with it.

This runs in $\Theta (p+q)=\Theta (n)$, the linear merge pattern. But it demands sorted halves, so we must sort them first: sorting $B$ and $C$ costs an extra $\Theta (n\log n)$ per level, and there are $\log n$ levels, giving $T(n)=2T(n/2)+\Theta (n\log n)=\Theta (n{\log }^{2}n)$. Better than quadratic, but the repeated sorting is wasteful.

Idea 2: sort and count in one pass. We are doing almost all of mergesort's work anyway, so let the recursion return both the inversion count and a sorted copy of its slice. Then the cross-counting merge also produces the sorted output the parent needs, for free.

The helper $\text{Count-Cross-Inv-And-Merge}$ is just $\text{Merge}$ with the counting rule from $\text{Count-Cross-Inv}$ folded in: whenever it takes from the right half because $A[mid+j]<A[i]$, it adds the number of elements still waiting in the left half. The combine step is now plain linear, so

This is the same recurrence as mergesort, and the same recursion tree explains it: $\log n$ levels, $\Theta (n)$ work each. Counting how disordered a list is costs no more, asymptotically, than sorting it.

Karatsuba multiplication: the same idea elsewhere

Sorting is not the only home for divide and conquer. Take a problem that feels unrelated: multiplying two large integers. Adding two $n$-bit numbers is easy. The grade-school ripple-carry method is $\Theta (n)$, and you cannot beat linear since you must at least read the input. Multiplication is the interesting one. The grade-school algorithm forms $n$ shifted partial products and adds them, costing $\Theta (n^2)$. Can divide and conquer do better?

Write each $n$-bit integer as a high half and a low half. With $n=2t$, split $x$ into its least-significant $t$ bits $a$ and its top $t$ bits $b$, and likewise split $y$ into $c$ and $d$:

Multiplying out $x=a+2^{t}b$ and $y=c+2^{t}d$ gives

The powers of two are just bit-shifts (free, up to the additions), so the cost is dominated by the four half-size products $ac$, $ad$, $bc$, $bd$. That yields $T(n)\le 4T(n/2)+bn$. Unrolling shows this is no improvement at all:

At $i={\log }_{2}n$ the leaf term is $4^{{\log }_{2}n}T(1)=n^{2}T(1)$, which dominates everything: $T(n)=\Theta (n^2)$. Splitting bought us nothing, because $a=4$ subproblems of half size is exactly the quadratic regime.

Karatsuba's trick is to compute the middle coefficient $ad+bc$ without a third and fourth multiplication. Notice the algebraic identity

We were going to compute $ac$ and $bd$ anyway. So once we have those two products, the middle term needs only one more multiplication, $(a-b)(d-c)$, plus a few additions. Three half-size products suffice:

Now $a=3$ recursive calls, each on half-size inputs, with $\Theta (n)$ work to split, shift, and add:

The recursion tree makes the cost legible. Level $i$ has $3^i$ nodes, each doing $bn/2^i$ work, for a row total of $(3/2{)}^{i}bn$. The rows grow geometrically downward, so the leaves dominate:

using $n^{{\log }_{2}3}=(3/2{)}^{{\log }_{2}n}\cdot n$ (the identity $x^{{\log }_{a}y}=y^{{\log }_{a}x}$). Trading one multiplication for a handful of additions drops integer multiplication below quadratic. The lesson generalizes: the number of subproblems, not just their size, drives the asymptotics, which is exactly what the master theorem makes precise. (Pushing the same idea to more than two chunks leads to the Fast Fourier Transform and $O(n\log n\log \log n)$ multiplication.)

Strassen's matrix multiplication

The same spend additions to save a multiplication idea cracks the cubic barrier for matrix multiplication. The schoolbook method costs $\Theta (n^3)$: each of the $n^2$ entries of $C=AB$ is a length-$n$ dot product. Divide and conquer splits each $n\times n$ matrix into four $(n/2)\times (n/2)$ blocks, and the product is read off block by block exactly as for $2\times 2$ scalars:

Taken at face value, the four output blocks need eight block multiplications, giving $T(n)=8T(n/2)+\Theta (n^2)$. The master theorem (next section) returns $\Theta (n^{{\log }_{2}8})=\Theta (n^3)$: more subproblems exactly cancel their smaller size, so blocking alone buys nothing.

Strassen's 1969 insight is that seven products suffice.⁴ Form seven recursive $(n/2)$-size multiplications,

and recover the output blocks by addition only:

The eighth multiplication is gone, traded for a handful of extra block additions that cost only $\Theta (n^2)$. The recurrence becomes $T(n)=7T(n/2)+\Theta (n^2)$, and now the leaves win:

The constant is large, so the crossover with the cubic method only pays off for sizable $n$; in practice Strassen is switched in above a threshold and the base case falls back to the cache-friendly schoolbook multiply. Theoretically, though, it was the first crack in the $\Theta (n^3)$ wall, and a long line of refinements has pushed the exponent down toward $2.37$.

The master theorem

Every recurrence in this lesson has the form $T(n)=aT(n/b)+\Theta (n^c)$. The recursion-tree analysis we did by hand each time generalizes to a single rule. Compare the branching exponent ${\log }_{b}a$, the rate at which leaves proliferate, against the work exponent $c$:

The three cases are exactly the three shapes of recursion tree: when ${\log }_{b}a>c$ the rows grow toward the leaves (Karatsuba), when they are equal every row costs the same (mergesort), and when ${\log }_{b}a<c$ the root's work dominates. Reading off our examples:

One last sanity check worth stressing: it makes no difference whether the combine cost is written $\Theta (n)$ or bounded above by $O(n)$. The recurrences $T(n)=2T(n/2)+\Theta (n)$ and $T(n)\le 2T(n/2)+O(n)$ have the same solution. The master theorem cares only about $a$, $b$, and the exponent $c$.

Takeaways

• Divide and conquer = divide into smaller copies, conquer recursively, combine. Trust the recursion; focus on the split and the merge. The cost is always a recurrence $T(n)=aT(n/b)+\Theta (n^c)$.
• $\text{Mergesort}$ divides at the midpoint and combines with a linear-time $\text{Merge}$ whose correctness is a clean loop-invariant argument.
• The recurrence $T(n)=2T(n/2)+\Theta (n)$ unfolds into a recursion tree with $\log n$ levels of $\Theta (n)$ work each, giving $\Theta (n\log n)$.
• Mergesort is stable and worst-case optimal among comparison sorts, at the cost of $\Theta (n)$ extra space, ideal for linked lists and external sorting.
• Counting inversions reuses the merge: fold a cross-inversion count into $\text{Merge}$ so each step adds $p-i+1$, sorting and counting together in $\Theta (n\log n)$ instead of the brute-force $\Theta (n^2)$.
• Karatsuba multiplication shows the paradigm's reach: the identity $ad+bc=(a-b)(d-c)+ac+bd$ cuts four subproblems to three, taking integer multiplication from $\Theta (n^2)$ to $\Theta (n^{{\log }_{2}3})$.
• The master theorem turns the tree into a rule: compare ${\log }_{b}a$ to $c$ for leaf-heavy, balanced, or root-heavy behavior.⁵