---
title: Divide and Conquer & Mergesort
module: Divide & Conquer
moduleNumber: 2
lessonNumber: 1
order: 201
summary: |
  Divide and conquer breaks a problem into smaller copies of itself, solves
  them recursively, and stitches the answers together. We meet the paradigm
  through mergesort — its merge step, its loop-invariant proof, and the
  recursion tree that pins its cost at $\Theta(n\log n)$ — then count inversions
  with the same machinery and distill the whole pattern into the master theorem.
topics: [Divide & Conquer, Comparison Sorting]
sources:
  - book: CLRS
    ref: "Ch. 2 & Ch. 4 — Getting Started; Divide-and-Conquer"
  - book: Skiena
    ref: "§4 — Sorting and Searching"
  - book: Erickson
    ref: "Ch. 1 — Recursion"
practice:
  - title: 'Merge Sorted Array'
    slug: merge-sorted-array
    difficulty: Easy
  - title: 'Sort an Array'
    slug: sort-an-array
    difficulty: Medium
  - title: 'Merge k Sorted Lists'
    slug: merge-k-sorted-lists
    difficulty: Hard
  - title: 'Count of Smaller Numbers After Self'
    slug: count-of-smaller-numbers-after-self
    difficulty: Hard
  - title: 'Reverse Pairs'
    slug: reverse-pairs
    difficulty: Hard
---

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"[^erickson-rec]
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

$$
T(n) = a\,T(n/b) + \Theta(n^c).
$$

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](/algorithms/foundations/recurrences) 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:

> **Input:** a sequence $\vector{a_1, a_2, \dots, a_n}$ of $n$ numbers.
> **Output:** a permutation $\vector{a'_1, \dots, a'_n}$ with
> $a'_1 \le a'_2 \le \cdots \le a'_n$.

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.
Ask: _if I already had two sorted halves, could I finish the
job cheaply?_ The answer, yes, by merging, gives us **mergesort**.[^clrs-merge]

## Mergesort

To sort the subarray $A[p..r]$, split it at the midpoint
$q = \floor{(p + r)/2}$, 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.

$$
% caption: Mergesort on $\langle 5,2,4,7,1,3,2,6\rangle$. The top half divides (black
%          arrows) down to singletons — the base cases; the bottom half merges (blue
%          arrows) those sorted runs back up, pair by pair, to the final sorted list.
\begin{tikzpicture}[font=\scriptsize, >={Stealth[round]},
  every node/.style={draw, minimum height=5mm, inner sep=2pt, font=\scriptsize},
  divide/.style={->}, merge/.style={->, acc, thick}]
  \definecolor{acc}{HTML}{2348F2}
  % --- divide (top half) ---
  \node (a) at (0,3) {$5\ 2\ 4\ 7\ 1\ 3\ 2\ 6$};
  \node (b) at (-2.6,2) {$5\ 2\ 4\ 7$};
  \node (c) at (2.6,2) {$1\ 3\ 2\ 6$};
  \node (d) at (-3.9,1) {$5\ 2$};
  \node (e) at (-1.3,1) {$4\ 7$};
  \node (f) at (1.3,1) {$1\ 3$};
  \node (g) at (3.9,1) {$2\ 6$};
  \node[fill=acc!12] (h) at (-4.5,0) {$5$};
  \node[fill=acc!12] (i) at (-3.3,0) {$2$};
  \node[fill=acc!12] (j) at (-1.9,0) {$4$};
  \node[fill=acc!12] (k) at (-0.7,0) {$7$};
  \node[fill=acc!12] (l) at (0.7,0) {$1$};
  \node[fill=acc!12] (m) at (1.9,0) {$3$};
  \node[fill=acc!12] (n) at (3.3,0) {$2$};
  \node[fill=acc!12] (o) at (4.5,0) {$6$};
  \draw[divide] (a) -- (b); \draw[divide] (a) -- (c);
  \draw[divide] (b) -- (d); \draw[divide] (b) -- (e);
  \draw[divide] (c) -- (f); \draw[divide] (c) -- (g);
  \draw[divide] (d) -- (h); \draw[divide] (d) -- (i);
  \draw[divide] (e) -- (j); \draw[divide] (e) -- (k);
  \draw[divide] (f) -- (l); \draw[divide] (f) -- (m);
  \draw[divide] (g) -- (n); \draw[divide] (g) -- (o);
  % --- merge (bottom half) ---
  \node (p1) at (-3.9,-1.4) {$2\ 5$};
  \node (p2) at (-1.3,-1.4) {$4\ 7$};
  \node (p3) at (1.3,-1.4) {$1\ 3$};
  \node (p4) at (3.9,-1.4) {$2\ 6$};
  \node (q1) at (-2.6,-2.6) {$2\ 4\ 5\ 7$};
  \node (q2) at (2.6,-2.6) {$1\ 2\ 3\ 6$};
  \node[fill=acc!18, draw=acc, very thick] (fin) at (0,-3.8) {$1\ 2\ 2\ 3\ 4\ 5\ 6\ 7$};
  \draw[merge] (h) -- (p1); \draw[merge] (i) -- (p1);
  \draw[merge] (j) -- (p2); \draw[merge] (k) -- (p2);
  \draw[merge] (l) -- (p3); \draw[merge] (m) -- (p3);
  \draw[merge] (n) -- (p4); \draw[merge] (o) -- (p4);
  \draw[merge] (p1) -- (q1); \draw[merge] (p2) -- (q1);
  \draw[merge] (p3) -- (q2); \draw[merge] (p4) -- (q2);
  \draw[merge] (q1) -- (fin); \draw[merge] (q2) -- (fin);
  \node[draw=none, black, font=\scriptsize] at (-5.7,1) {divide};
  \node[draw=none, acc, font=\scriptsize] at (-5.7,-2.6) {merge};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Merge-Sort}(A, p, r)$ — sort $A[p..r]$ in increasing order
number: 1
if $p < r$ then
  $q \gets \floor{(p + r) / 2}$ // split point
  call $\textsc{Merge-Sort}(A, p, q)$ // sort left half
  call $\textsc{Merge-Sort}(A, q + 1, r)$ // sort right half
  call $\textsc{Merge}(A, p, q, r)$ // combine halves
```

All the real work lives in the **combine** step. $\textsc{Merge}$ takes two adjacent
sorted runs, $A[p..q]$ and $A[q+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.

```algorithm
caption: $\textsc{Merge}(A, p, q, r)$ — merge sorted $A[p..q]$ and $A[q+1..r]$
number: 2
$n_1 \gets q - p + 1$
$n_2 \gets r - q$
let $L[1..n_1 + 1]$ and $R[1..n_2 + 1]$ be new arrays
for $i \gets 1$ to $n_1$ do
  $L[i] \gets A[p + i - 1]$ // copy left half
for $j \gets 1$ to $n_2$ do
  $R[j] \gets A[q + j]$ // copy right half
$L[n_1 + 1] \gets \infty$ // sentinel guards the run end
$R[n_2 + 1] \gets \infty$
$i \gets 1$
$j \gets 1$
for $k \gets p$ to $r$ do
  if $L[i] \le R[j]$ then
    $A[k] \gets L[i]$
    $i \gets i + 1$
  else
    $A[k] \gets R[j]$
    $j \gets j + 1$
```

::impl{algo="mergesort"}

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.

$$
% caption: Merge step with cursors $i$ and $j$ on sorted runs $L$ and $R$ writing the
%          smaller value into $A$ at $k$. The last cell of each run holds the
%          sentinel $\infty$.
\begin{tikzpicture}[
  font=\small,
  cell/.style={draw, minimum width=8mm, minimum height=8mm},
  lbl/.style={font=\scriptsize\itshape},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  % left run L (cursor at index 3, value 11)
  \node[lbl] at (-1.1, 1.4) {$L$};
  \node[cell] at (0,1.4) {$2$};
  \node[cell] at (1,1.4) {$5$};
  \node[cell, fill=acc!12] at (2,1.4) {$11$};
  \node[cell] at (3,1.4) {$17$};
  \node[cell] at (4,1.4) {};
  \draw (3.905,1.4) circle (0.082) (4.095,1.4) circle (0.082);
  \node[lbl, acc] at (2,2.3) {$i$};
  \draw[->, acc] (2,2.05) -- (2,1.85);
  % right run R (cursor at index 2, value 8) -- the smaller, so the winner
  \node[lbl] at (-1.1, 0) {$R$};
  \node[cell] at (0,0) {$3$};
  \node[cell, fill=acc!15, draw=acc, very thick] at (1,0) {$8$};
  \node[cell] at (2,0) {$15$};
  \node[cell] at (3,0) {};
  \draw (2.905,0) circle (0.082) (3.095,0) circle (0.082);
  \node[lbl, acc] at (1,-0.9) {$j$};
  \draw[->, acc] (1,-0.65) -- (1,-0.2);
  % output A (filled through index 2)
  \node[lbl] at (-1.1, -1.8) {$A$};
  \node[cell, fill=black!7] at (0,-1.8) {$2$};
  \node[cell, fill=black!7] at (1,-1.8) {$3$};
  \node[cell, fill=black!7] at (2,-1.8) {$5$};
  \node[cell, fill=acc!15, draw=acc, very thick] (Ak) at (3,-1.8) {};
  \node[cell] at (4,-1.8) {};
  \node[lbl, acc] at (3,-2.7) {$k$};
  \draw[->, acc] (3,-2.45) -- (3,-2.0);
  % the smaller of L[i]=11, R[j]=8 is 8 -> written to A[k]: clean arc from R[j] east down to A[k] top, kept left of the right margin so the caption sits clear of every cell and label
  \draw[->, red!75!black, thick] (1.42,0) to[out=-35, in=125] (3,-1.38);
  \node[lbl, red!75!black, anchor=west, align=left] at (4.5,-0.9)
    {min of $L[i]$, $R[j]$\\ written to $A[k]$};
\end{tikzpicture}
$$

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:

> **Invariant (Merge loop invariant).** _At the start of each iteration of the **for** loop, the subarray
> $A[p..k-1]$ contains the $k - p$ smallest elements of $L$ and $R$, in sorted
> order. Also $L[i]$ and $R[j]$ are the smallest elements of their arrays
> not yet copied back._

> **Proof.** By initialization, maintenance, termination.
> - **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. $\qed$

For example, run the loop to completion on the two halves $\langle 2,4,5,7\rangle$ and
$\langle 1,2,3,6\rangle$. After the copy phase,
$L = \langle 2,4,5,7,\infty\rangle$ and $R = \langle 1,2,3,6,\infty\rangle$.
Each row below is one iteration of the **for** loop: one comparison, one write,
one cursor advance.

| $k$ | comparison | winner | $A[p..k]$ after the write |
| --- | --- | --- | --- |
| $1$ | $L[1]=2$ vs $R[1]=1$ | $R$ | $\langle 1\rangle$ |
| $2$ | $L[1]=2$ vs $R[2]=2$ | $L$ (tie: $\le$ takes left) | $\langle 1,2\rangle$ |
| $3$ | $L[2]=4$ vs $R[2]=2$ | $R$ | $\langle 1,2,2\rangle$ |
| $4$ | $L[2]=4$ vs $R[3]=3$ | $R$ | $\langle 1,2,2,3\rangle$ |
| $5$ | $L[2]=4$ vs $R[4]=6$ | $L$ | $\langle 1,2,2,3,4\rangle$ |
| $6$ | $L[3]=5$ vs $R[4]=6$ | $L$ | $\langle 1,2,2,3,4,5\rangle$ |
| $7$ | $L[4]=7$ vs $R[4]=6$ | $R$ | $\langle 1,2,2,3,4,5,6\rangle$ |
| $8$ | $L[4]=7$ vs $R[5]=\infty$ | $L$ | $\langle 1,2,2,3,4,5,6,7\rangle$ |

Two rows deserve a second look. At $k = 2$ the fronts tie at $2$; the $\le$
comparison takes from $L$, the left half — the choice that makes the sort
stable (more on this below). At $k = 8$ the right run is exhausted and its front
is the sentinel $\infty$, so the comparison automatically drains the rest of
$L$ with no special end-of-run test. Eight iterations, eight writes, each
element landing in its sorted slot:

$$
% caption: The completed merge of sorted halves $\langle 2,4,5,7\rangle$ and
%          $\langle 1,2,3,6\rangle$ interleaves into one sorted run.
\begin{tikzpicture}[font=\small, >={Stealth[round]},
  cell/.style={draw, minimum width=7mm, minimum height=7mm, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  \node[font=\scriptsize\itshape] at (-1.4,1) {two runs};
  \foreach \v/\x in {2/0,4/1,5/2,7/3} \node[cell] at (\x,1) {$\v$};
  \foreach \v/\x in {1/4.4,2/5.4,3/6.4,6/7.4} \node[cell, fill=acc!12] at (\x,1) {$\v$};
  \node[font=\scriptsize\itshape] at (-1.4,-0.4) {output};
  \foreach \v/\x in {1/0,2/1,2/2,3/3,4/4,5/5,6/6,7/7} \node[cell, fill=black!7] at (\x,-0.4) {$\v$};
\end{tikzpicture}
$$

## 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 $2\,T(n/2)$, and the
merge costs $\Theta(n)$. So

$$
T(n) = 2\,T(n/2) + \Theta(n), \qquad T(1) = \Theta(1).
$$

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.

$$
% caption: Recursion tree for mergesort with _each_ node showing its merge cost, summing
%          to $cn$ per level.
\begin{tikzpicture}[level distance=14mm,
  level 1/.style={sibling distance=46mm},
  level 2/.style={sibling distance=23mm},
  every node/.style={draw, minimum size=7mm, font=\small}]
  \node {$cn$}
    child {node {$\tfrac{cn}{2}$}
      child {node {$\tfrac{cn}{4}$}}
      child {node {$\tfrac{cn}{4}$}}}
    child {node {$\tfrac{cn}{2}$}
      child {node {$\tfrac{cn}{4}$}}
      child {node {$\tfrac{cn}{4}$}}};
\end{tikzpicture}
$$

**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$.

$$
% caption: Doubling the node count while halving each node's work keeps every level's
%          total fixed at $cn$; the $\log_2 n + 1$ rows give $\Theta(n\log n)$.
\begin{tikzpicture}[font=\scriptsize, >={Stealth[round]}, x=1cm, y=1cm]
  \definecolor{acc}{HTML}{2348F2}
  \node[draw, fill=acc!10, minimum width=10mm] (a) at (0,2) {$cn$};
  \node[draw, minimum width=8mm] (b) at (-1.6,1) {$\tfrac{cn}{2}$};
  \node[draw, minimum width=8mm] (c) at (1.6,1) {$\tfrac{cn}{2}$};
  \node[draw, minimum width=6mm] (d) at (-2.6,0) {$\tfrac{cn}{4}$};
  \node[draw, minimum width=6mm] (e) at (-0.7,0) {$\tfrac{cn}{4}$};
  \node[draw, minimum width=6mm] (f) at (0.7,0) {$\tfrac{cn}{4}$};
  \node[draw, minimum width=6mm] (g) at (2.6,0) {$\tfrac{cn}{4}$};
  \draw[->] (a)--(b); \draw[->] (a)--(c);
  \draw[->] (b)--(d); \draw[->] (b)--(e);
  \draw[->] (c)--(f); \draw[->] (c)--(g);
  \draw[densely dashed, acc] (3.6,2) -- (5.3,2);
  \draw[densely dashed, acc] (3.6,1) -- (5.3,1);
  \draw[densely dashed, acc] (3.6,0) -- (5.3,0);
  \node[anchor=west, acc] at (3.7,2.28) {row sum $=cn$};
  \node[anchor=west, acc] at (3.7,1.28) {row sum $=cn$};
  \node[anchor=west, acc] at (3.7,0.28) {row sum $=cn$};
\end{tikzpicture}
$$

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:

$$
T(n) = cn \cdot (\log_2 n + 1) = \Theta(n\log n).
$$

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

> **Property (Stability).** Mergesort is **stable**: equal elements keep their
> original relative order.

This falls out of the $\le$ in $\textsc{Merge}$: when $L[i] = R[j]$ we take from
$L$, the _left_ (earlier) half, first. We saw it happen in the trace above, at
$k = 2$: the two front elements tied at $2$, and the left half's copy was
emitted first. Since every element of $L$ came from earlier positions in $A$
than every element of $R$, and recursion preserves the property inductively,
equal elements never swap places.

$$
% caption: Stability on $\langle 3_a, 1, 3_b, 2, 3_c\rangle$: the three equal keys
%          (subscripts mark original order) arrive in the output in the same
%          left-to-right order they started in.
\begin{tikzpicture}[font=\small, >={Stealth[round]},
  cell/.style={draw, minimum width=8mm, minimum height=8mm, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  \node[font=\scriptsize\itshape] at (-1.4,1.5) {input};
  \node[cell, fill=acc!14] (t0) at (0,1.5) {$3_a$};
  \node[cell] (t1) at (1,1.5) {$1$};
  \node[cell, fill=acc!14] (t2) at (2,1.5) {$3_b$};
  \node[cell] (t3) at (3,1.5) {$2$};
  \node[cell, fill=acc!14] (t4) at (4,1.5) {$3_c$};
  \node[font=\scriptsize\itshape] at (-1.4,-0.4) {output};
  \node[cell] (b0) at (0,-0.4) {$1$};
  \node[cell] (b1) at (1,-0.4) {$2$};
  \node[cell, fill=acc!14] (b2) at (2,-0.4) {$3_a$};
  \node[cell, fill=acc!14] (b3) at (3,-0.4) {$3_b$};
  \node[cell, fill=acc!14] (b4) at (4,-0.4) {$3_c$};
  \draw[->, acc] (t0.south) -- (b2.north);
  \draw[->, acc] (t2.south) -- (b3.north);
  \draw[->, acc] (t4.south) -- (b4.north);
  \draw[->, black] (t1.south) -- (b0.north);
  \draw[->, black] (t3.south) -- (b1.north);
\end{tikzpicture}
$$

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. Sorting employees by department after sorting them by name
leaves each department's roster alphabetized — but only if the second sort is
stable.

## Mergesort versus other sorts

| Property | Mergesort | Insertion sort | Heapsort | Quicksort |
| --- | --- | --- | --- | --- |
| Worst case | $\Theta(n\log n)$ | $\Theta(n^2)$ | $\Theta(n\log n)$ | $\Theta(n^2)$ |
| Average case | $\Theta(n\log n)$ | $\Theta(n^2)$ | $\Theta(n\log n)$ | $\Theta(n\log n)$ |
| Extra space | $\Theta(n)$ | $\Theta(1)$ | $\Theta(1)$ | $\Theta(\log n)$ |
| Stable | yes | yes | no | no |
| In place | no | yes | yes | yes |

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.[^skiena-sort] Its cost is the $\Theta(n)$
auxiliary array. [Quicksort](/algorithms/divide-and-conquer/quicksort), the subject of the next lesson, trades that
guarantee for better constants and in-place operation.

## When the recursion is not worth it

Divide and conquer wins _asymptotically_, but each recursive call carries real
overhead: stack frames, index arithmetic, the scratch-array traffic of
$\textsc{Merge}$. On a subarray of ten elements, insertion sort's tight loop with
no allocation beats all of that machinery outright. Two standard adjustments
exploit this.

**Cut off to insertion sort.** Stop recursing once the subarray shrinks below a
threshold $k$ and finish it with insertion sort. The $n/k$ base cases cost
$\Theta(k^2)$ each, for $\Theta(nk)$ total, while the merging now spans only
$\log(n/k)$ levels of $\Theta(n)$ work apiece:

$$
T(n) = \Theta\!\parens{nk + n\log(n/k)}.
$$

For constant $k$ this is still $\Theta(n\log n)$ — the asymptotics are
untouched — but the constant factor drops because the bottom $\log k$ levels of
the recursion tree, the levels with the most nodes and the most per-call
overhead, are replaced by a handful of cheap quadratic sorts. In practice $k$
is tuned somewhere between $8$ and $32$.

**Go bottom-up.** The recursion can be removed entirely. Bottom-up mergesort
treats the array as $n$ sorted runs of width $1$, then makes passes that merge
adjacent runs pairwise: after the first pass the runs have width $2$, then $4$,
then $8$, doubling until one run remains.

$$
% caption: Bottom-up mergesort on $\langle 5,2,4,7,1,3,2,6\rangle$: each pass merges
%          adjacent runs pairwise, doubling the run width, with no recursion at all.
\begin{tikzpicture}[font=\small, >={Stealth[round]},
  cell/.style={draw, minimum width=8mm, minimum height=8mm, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % width-1 runs
  \node[font=\scriptsize, anchor=west] at (8.0,0) {runs of 1};
  \foreach \v/\x in {5/0,2/1,4/2,7/3,1/4,3/5,2/6,6/7} \node[cell] at (\x,0) {$\v$};
  % width-2 runs
  \node[font=\scriptsize, anchor=west] at (8.0,-1.3) {runs of 2};
  \foreach \v/\x in {2/0,5/1,4/2,7/3,1/4,3/5,2/6,6/7} \node[cell, fill=acc!6] at (\x,-1.3) {$\v$};
  \foreach \x in {1.5,3.5,5.5} \draw[acc, thick] (\x,-1.7) -- (\x,-0.9);
  % width-4 runs
  \node[font=\scriptsize, anchor=west] at (8.0,-2.6) {runs of 4};
  \foreach \v/\x in {2/0,4/1,5/2,7/3,1/4,2/5,3/6,6/7} \node[cell, fill=acc!12] at (\x,-2.6) {$\v$};
  \draw[acc, thick] (3.5,-3.0) -- (3.5,-2.2);
  % sorted
  \node[font=\scriptsize, anchor=west] at (8.0,-3.9) {one run};
  \foreach \v/\x in {1/0,2/1,2/2,3/3,4/4,5/5,6/6,7/7} \node[cell, fill=acc!18] at (\x,-3.9) {$\v$};
\end{tikzpicture}
$$

Each pass is a plain loop over the array doing $\Theta(n)$ merge work, and
there are $\ceil{\log_2 n}$ passes, so the cost is the same $\Theta(n\log n)$ —
the recursion tree read bottom-to-top instead of top-to-bottom. What iteration
buys is engineering: no stack, no function-call overhead, and a shape that
suits linked lists (splice runs instead of copying) and external sorting, where
each pass is one sequential sweep over the data on disk. What it gives up is
the cutoff trick's easy hybridization and any chance to exploit runs that are
already sorted — refinements that top-down and bottom-up variants alike can
bolt back on.

The broader moral: divide and conquer sets the asymptotic ceiling, but at small
sizes a simple iterative method with better constants wins, so real
implementations are hybrids — recursion (or doubling passes) for the large
scales, iteration for the base.

## 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
$\vector{a_1, a_2, \dots, a_n}$, how _close to sorted_ is it? A natural measure
counts the pairs that are out of order.

> **Input:** an array $A[1..n]$.
> **Output:** $\ninv(A)$, the number of **inversions** — pairs
> $(i, j)$ with $1 \le i < j \le n$ and $A[i] > A[j]$.

A sorted array has zero inversions; a reverse-sorted one has the maximum,
$\binom{n}{2}$. (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 $\binom{n}{2} = \tfrac12 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]$.

$$
% caption: A cross inversion linking an element in left half $B$ to a smaller element in
%          right half $C$.
\begin{tikzpicture}[font=\small, >={Stealth[round]}]
  \draw (0,0) rectangle (3.2,0.9); \node at (1.6,0.6) {$B$ (left half)};
  \draw (3.2,0) rectangle (6.4,0.9); \node at (4.8,0.6) {$C$ (righ\/t half)};
  \node[circle, fill=red!70!black, inner sep=1.3pt] (b) at (1.0,0.3) {};
  \node[circle, fill=red!70!black, inner sep=1.3pt] (c) at (4.4,0.3) {};
  \draw[->, red!70!black, thick] (b) to[bend right=12] (c);
  \node[red!70!black, font=\scriptsize] at (3.2,1.25)
    {\texttt{cross inversion}: $B[i] > C[j]$};
\end{tikzpicture}
$$

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 $\textsc{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 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.

$$
% caption: When the merge finds $B[i] > C[j]$, sortedness of $B$ means every remaining
%          $B[i..p]$ also exceeds $C[j]$ — so emitting $C[j]$ adds $p-i+1$ cross
%          inversions in one stroke.
\begin{tikzpicture}[font=\small, >={Stealth[round]},
  cell/.style={draw, minimum width=8mm, minimum height=8mm, font=\small}]
  \definecolor{acc}{HTML}{2348F2}
  % left run B (sorted), cursor i at value 6; B[i..p] = 6,8,9 all > C[j]
  \node[font=\scriptsize\itshape] at (-1.2,1.4) {$B$};
  \node[cell] at (0,1.4) {$2$};
  \node[cell] at (1,1.4) {$5$};
  \node[cell, fill=acc!15] at (2,1.4) {$6$};
  \node[cell, fill=acc!15] at (3,1.4) {$8$};
  \node[cell, fill=acc!15] at (4,1.4) {$9$};
  \node[font=\scriptsize\itshape, acc] at (1.4,2.15) {$i$};
  \draw[->, acc] (1.55,2.0) -- (1.85,1.85);
  \draw[acc] (1.55,2.05) -- (4.45,2.05) node[midway, above, font=\scriptsize] {B[i..p], all $>$ C[j]};
  % right run C, cursor j at value 4 (the small one being emitted)
  \node[font=\scriptsize\itshape] at (-1.2,-1.4) {$C$};
  \node[cell, fill=acc!15, draw=acc, very thick] at (2,-1.4) {$4$};
  \node[cell] at (3,-1.4) {$7$};
  \node[font=\scriptsize\itshape, acc] at (2,-2.25) {$j$};
  \draw[->, acc] (2,-2.0) -- (2,-1.85);
  % red fan from C[j] up to each of the three B elements: p-i+1 = 3 inversions at once
  \foreach \tx in {2,3,4} \draw[->, red!75!black, thick] (2,-1.05) -- (\tx,1.05);
  \node[font=\scriptsize, red!75!black, anchor=west, align=left] at (5.0,-0.0)
    {\texttt{C[j] inverts with all}\\ \texttt{p-i+1 = 3 of B[i..p]}};
\end{tikzpicture}
$$

```algorithm
caption: $\textsc{Count-Cross-Inv}(B[1..p], C[1..q])$ — cross inversions, $B, C$ sorted
number: 3
$\mathit{ans} \gets 0$
$i \gets 1$
$j \gets 1$
while $i \le p$ and $j \le q$ do
  if $B[i] \le C[j]$ then
    $i \gets i + 1$ // no inversion
  else
    $\mathit{ans} \gets \mathit{ans} + (p - i + 1)$ // $C[j]$ inverts with $B[i..p]$
    $j \gets j + 1$
return $\mathit{ans}$
```

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.

```algorithm
caption: $\textsc{Sort-And-Count-Inv}(A, \mathit{lo}, \mathit{hi})$ — sort $A[\mathit{lo}..\mathit{hi}]$, return its inversion count
number: 4
if $\mathit{hi} \le \mathit{lo}$ then
  return $0$ // single element: no inversions
$t \gets \floor{(\mathit{lo} + \mathit{hi}) / 2}$
$c \gets \textsc{Sort-And-Count-Inv}(A, \mathit{lo}, t)$ // left inversions + sort left
$c \gets c + \textsc{Sort-And-Count-Inv}(A, t + 1, \mathit{hi})$ // right inversions + sort right
$c \gets c + \textsc{Count-Cross-Inv-And-Merge}(A, \mathit{lo}, t, \mathit{hi})$ // cross + merge
return $c$
```

::impl{algo="count_inversions"}

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

$$
T(n) = 2\,T(n/2) + \Theta(n) = \Theta(n \log n).
$$

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](/algorithms/foundations/asymptotic-analysis), than sorting it.

### A worked count

Run the algorithm on $A = \langle 2,4,1,3,5\rangle$, whose inversions are
$(2,1)$, $(4,1)$, and $(4,3)$ — three in all. The split gives
$B = \langle 2,4\rangle$ and $C = \langle 1,3,5\rangle$. Both halves are
already sorted, so the recursive calls return $0$ and $0$, and everything rides
on the counting merge:

| step | fronts | action | count added | running total |
| --- | --- | --- | --- | --- |
| $1$ | $B{:}\,2$ vs $C{:}\,1$ | emit $1$ from $C$ | $2$ (both of $\langle 2,4\rangle$ exceed $1$) | $2$ |
| $2$ | $B{:}\,2$ vs $C{:}\,3$ | emit $2$ from $B$ | $0$ | $2$ |
| $3$ | $B{:}\,4$ vs $C{:}\,3$ | emit $3$ from $C$ | $1$ (only $4$ remains in $B$) | $3$ |
| $4$ | $B{:}\,4$ vs $C{:}\,5$ | emit $4$ from $B$ | $0$ | $3$ |
| $5$ | $B$ empty | emit $5$ from $C$ | $0$ | $3$ |

Total: $0 + 0 + 3 = 3$, matching the hand count, and the array leaves the merge
sorted as $\langle 1,2,3,4,5\rangle$, ready for use by the parent call. Step $1$
is the batching in action: one comparison charged _two_ inversions, because
sortedness of $B$ guarantees every element from its cursor onward exceeds the
emitted value.

## Beyond sorting: faster multiplication

Sorting is not the only home for divide and conquer. The same paradigm beats the
grade-school $\Theta(n^2)$ algorithm for multiplying large integers
(**Karatsuba**, three half-size products instead of four, $\Theta(n^{\log_2 3})$)
and the cubic schoolbook algorithm for multiplying matrices (**Strassen**, seven
block products instead of eight, $\Theta(n^{\log_2 7})$). Both spend cheap
additions to buy back an expensive multiplication, and both fall straight out of
the master theorem below. We give them a lesson of their own:
[Fast Multiplication](/algorithms/divide-and-conquer/fast-multiplication).

## The master theorem

Every recurrence in this lesson has the form $T(n) = a\,T(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$:

$$
T(n) = a\,T(n/b) + \Theta(n^{c}) \quad\Longrightarrow\quad
T(n) =
\begin{cases}
\Theta\!\parens{n^{\log_b a}} & \text{if } \log_b a > c
  & \text{(leaf-heavy)} \\[2pt]
\Theta\!\parens{n^{c}\log n} & \text{if } \log_b a = c
  & \text{(balanced)} \\[2pt]
\Theta\!\parens{n^{c}} & \text{if } \log_b a < c
  & \text{(root-heavy)} .
\end{cases}
$$

The three cases correspond to the three shapes of recursion tree: when
$\log_b a > c$ the rows grow toward the leaves
([Karatsuba](/algorithms/divide-and-conquer/fast-multiplication)), 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:

| Algorithm | Recurrence | $a$ | $b$ | $c$ | $\log_b a$ vs $c$ | $T(n)$ |
| --- | --- | --- | --- | --- | --- | --- |
| Mergesort | $2T(n/2) + \Theta(n)$ | $2$ | $2$ | $1$ | $1 = 1$, balanced | $\Theta(n\log n)$ |
| Counting inversions | $2T(n/2) + \Theta(n)$ | $2$ | $2$ | $1$ | $1 = 1$, balanced | $\Theta(n\log n)$ |
| Inversions, naive combine | $2T(n/2) + \Theta(n^2)$ | $2$ | $2$ | $2$ | $1 < 2$, root-heavy | $\Theta(n^2)$ |
| Karatsuba | $3T(n/2) + \Theta(n)$ | $3$ | $2$ | $1$ | $\log_2 3 > 1$, leaf-heavy | $\Theta(n^{\log_2 3})$ |

::impl{algo="master_theorem"}

One last sanity check: 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 depends only on $a$, $b$, and the exponent $c$.

## The sort real programs call

Mergesort's clean structure and stability make it the base for the sort that most
real programs actually call.

**Timsort: exploit the runs already there.** The default sort in Python's `list`
and Java's `Arrays.sort` for objects is **Timsort** (Tim Peters, 2002), an
adaptive, stable mergesort. Real data is rarely random: it arrives with long
stretches already ascending or descending — a log file appended over time, a list
re-sorted after a few edits. Timsort scans for these **natural runs** first,
reversing descending ones in place, and only merges the runs it finds, so an
already-sorted array costs a single $\Theta(n)$ pass instead of $\Theta(n\log n)$.
It extends short runs with an insertion sort up to a minimum length, and it merges
runs under a stack invariant that keeps run lengths balanced (the invariant had a
famous bug, found in 2015 by researchers formally verifying the merge policy, that
could overflow the merge stack — since fixed). The through-line is the bottom-up
idea from earlier, made adaptive: instead of blindly doubling from width $1$, start
from the runs already present in the input.

**Merging in parallel.** The recursion tree's independent subproblems make
mergesort a natural fit for multiple cores: the two recursive sorts run on separate
threads, and the join waits for both. But a naive parallel mergesort is bottlenecked
by its _sequential_ $\Theta(n)$ merge at the root. The fix is a **parallel merge**:
to merge two sorted halves, binary-search the median of one into the other to split
both into balanced pieces that merge independently, recursively. This drops the
span (critical-path length) to $\Theta(\log^2 n)$ while keeping the work
$\Theta(n\log n)$, the design behind the parallel sorts in libraries like Intel TBB
and the C++17 parallel `std::sort`. Mergesort's sequential, predictable access
pattern — the same property that suits linked lists and disk — also lets it
carve cleanly across cores.[^skiena-sort]

## 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) = a\,T(n/b) + \Theta(n^c)$.
- $\textsc{Mergesort}$ divides at the midpoint and combines with a linear-time
  $\textsc{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](/algorithms/sorting/sorting-lower-bounds), at the
  cost of $\Theta(n)$ extra space, ideal for linked lists and external sorting.
- At small sizes the recursion's overhead loses to plain iteration: real
  implementations cut off to insertion sort below a threshold ($\Theta(nk +
  n\log(n/k))$) or run **bottom-up**, merging width-$1, 2, 4, \dots$ runs with
  no recursion at all.
- **Counting inversions** reuses the merge: fold a cross-inversion count into
  $\textsc{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)$.
- The same machinery beats grade-school arithmetic — see
  [Fast Multiplication](/algorithms/divide-and-conquer/fast-multiplication) for
  Karatsuba ($\Theta(n^{\log_2 3})$) and Strassen ($\Theta(n^{\log_2 7})$).
- The **master theorem** turns the tree into a rule: compare $\log_b a$ to $c$
  for leaf-heavy, balanced, or root-heavy behavior.[^clrs-master]

[^erickson-rec]: **Erickson**, _Algorithms_, Ch. 1 — Recursion: the "recursion fairy" stance of assuming recursive calls already work and focusing on divide and combine.
[^clrs-merge]: **CLRS**, Ch. 2 (§2.3) — Designing algorithms: mergesort as the canonical divide-and-conquer sort built on a linear-time merge.
[^skiena-sort]: **Skiena**, _The Algorithm Design Manual_, §4 — Sorting and Searching: mergesort's stability and suitability for linked lists and external sorting.
[^clrs-master]: **CLRS**, Ch. 4 — Divide-and-Conquer: the master theorem comparing $\log_b a$ against the work exponent $c$ to classify leaf-heavy, balanced, and root-heavy recurrences.