Merge sort & divide-and-conquer

The divide-and-conquer template

Divide-and-conquer solves a problem by breaking it into smaller instances of *the same* problem:

- Divide the instance into subproblems. - Conquer each subproblem recursively (or directly, if small enough — the base case). - Combine the subsolutions into a solution for the original.

Merge sort is the canonical example. To sort $A[p..r]$: divide at the midpoint $q = \lfloor (p+r)/2 \rfloor$, recursively sort $A[p..q]$ and $A[q+1..r]$, then merge the two sorted halves. The recursion bottoms out at a one-element subarray ($p \ge r$), which is trivially sorted. Almost all the work lives in the combine step — the opposite of quicksort, where the work is in the divide.

MERGE is the engine, and it is Θ(n)

MERGE(A, p, q, r) assumes $A[p..q]$ and $A[q+1..r]$ are each already sorted, and weaves them into one sorted run. It copies the two halves into temporaries $L$ and $R$, then repeatedly appends the smaller of the two current front elements:

MERGE(L, R):
  i = j = 0; out = []
  while i < |L| and j < |R|
    if L[i] <= R[j]: out.append(L[i]); i = i + 1
    else:           out.append(R[j]); j = j + 1
  append the rest of L, then the rest of R
  return out

Why temporaries? Merging in place would overwrite values still needed for later comparisons. The cost: each of the $n = r - p + 1$ elements is moved from $A$ into $L/R$ and then back into $A$ exactly once, so MERGE runs in $\Theta(n)$ — and that linear merge is precisely what makes the whole sort $\Theta(n\lg n)$. Using <= (not <) in the comparison keeps merge sort stable.

The recurrence and its solution

Divide costs $\Theta(1)$ (a midpoint); conquer is $2T(n/2)$; combine is $\Theta(n)$. So:

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

Recursion-tree argument. Picture the tree of subproblem costs. Level $i$ has $2^i$ nodes, each of size $n/2^i$, so each node does $c \cdot n/2^i$ merge work — and the level's total is $2^i \cdot c\,n/2^i = c\,n$, the same at every level. The doubling of nodes exactly cancels the halving of cost-per-node. The tree has $\lg n + 1$ levels (you can halve $n$ down to $1$ exactly $\lg n$ times). So the total is

$$ \underbrace{c\,n}_{\text{per level}} \times \underbrace{(\lg n + 1)}_{\text{levels}} = c\,n\lg n + c\,n = \Theta(n\lg n). $$

Unlike insertion sort, merge sort's running time is $\Theta(n\lg n)$ in *all* cases — it always splits, always recurses, always merges, regardless of the input order. The price is $\Theta(n)$ extra space for the temporaries.