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+\mathrm{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+\mathrm{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),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 cn/2^i=cn$, 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

$$\underset{\text{per level}}{\underbrace{cn}}\times \underset{\text{levels}}{\underbrace{(\lg n+1)}}=cn\lg n+cn=\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.