7 · Divide & conquer + merge sort

In one sentence

Divide & conquer splits a problem into smaller copies of itself, solves them recursively, and combines the answers. Merge sort splits the array in half, sorts each half, then merges two sorted halves in linear time, for $\Theta(n\log n)$ in every case.

Everyday analogy

Sorting exam papers with friends. You have 800 papers. Give half to each of two friends; they each split their pile again, and so on, until each person holds one paper (already "sorted"). Then everyone walks back up the chain: two people with sorted piles merge them by repeatedly taking the smaller top sheet. Merging two sorted piles is fast, because you only ever look at the two top sheets.

Key ideas

Step	Merge sort	Cost
Divide	find the middle $q$	$\Theta(1)$
Conquer	sort `A[p..q]` and `A[q+1..r]` recursively	$2T(n/2)$
Combine	`Merge` the two sorted halves	$\Theta(n)$

T(n) = \begin{cases}\Theta(1) & n = 1\\ 2T(n/2) + \Theta(n) & n > 1\end{cases} \quad\Rightarrow\quad T(n) = \Theta(n\log n) \text{ (solved in Topic 8)}

MergeSort(A, p, r)
1  if p ≥ r then return                // 0 or 1 element: already sorted
2  q ← ⌊(p + r) / 2⌋
3  MergeSort(A, p, q)
4  MergeSort(A, q + 1, r)
5  Merge(A, p, q, r)

Merge(A, p, q, r)                      // A[p..q] and A[q+1..r] are each sorted
1  copy A[p..q] into L, A[q+1..r] into R
2  i ← 1; j ← 1; k ← p
3  while i ≤ |L| and j ≤ |R| do        // both piles still have cards
4      if L[i] ≤ R[j] then A[k] ← L[i]; i ← i + 1
5      else               A[k] ← R[j]; j ← j + 1
6      k ← k + 1
7  copy whatever is left in L or R into A[k..r]

Tree facts used in the analysis (complete $k$ -ary tree): level $d$ has $k^d$ nodes, and a tree with $n$ leaves has height $\log_k n$ . For merge sort ( $k = 2$ ): $\log_2 n$ splitting levels.

Merge sort on [6, 2, 9, 4, 1, 7, 3, 8] (our own example)

Merging back up (comparisons in brackets):

Level	Merges	Result
size 2	[6]+[2]→2 6 (1) · [9]+[4]→4 9 (1) · [1]+[7]→1 7 (1) · [3]+[8]→3 8 (1)	4 comparisons
size 4	[2 6]+[4 9]→2 4 6 9 (3) · [1 7]+[3 8]→1 3 7 8 (3)	6 comparisons
size 8	[2 4 6 9]+[1 3 7 8]→1 2 3 4 6 7 8 9 (7)	7 comparisons

Total 17 comparisons. Each level does at most $n = 8$ work, and there are $\log_2 8 = 3$ merge levels.

Inside one merge: L = [2 4 6 9], R = [1 3 7 8]

compare	take	output so far
2 vs 1	1 (R)	1
2 vs 3	2 (L)	1 2
4 vs 3	3 (R)	1 2 3
4 vs 7	4 (L)	1 2 3 4
6 vs 7	6 (L)	1 2 3 4 6
9 vs 7	7 (R)	1 2 3 4 6 7
9 vs 8	8 (R)	1 2 3 4 6 7 8
R empty	copy 9	1 2 3 4 6 7 8 9

Common mistakes

In a trace, merging unsorted halves. Always recurse all the way down first.
Forgetting to copy the leftovers at the end of Merge.
Saying merge sort is $\Theta(n)$ in the best case. It does the same splitting and merging on every input.
Miscounting levels: there are $\log_2 n$ merge levels plus the leaf level, so $\log_2 n + 1$ levels in the tree.

Mastery check

Solve without hints, then explain

Trace merge sort on [5, 1, 4, 2, 8, 3] (left half gets the extra element when splitting an odd size). Show every merge and count the total comparisons.

Your mastery check

Not started

Solve the problem above with no hints, close the page and explain it out loud. Tick each step honestly.

Solved the mastery check with no hints

Said it in one sentence

Explained it with my own analogy

Walked through the steps of my own hand trace

Explained why it is correct / how fast it is

Named a trap a beginner would fall into

Status

Tick all six steps to unlock “Mastered”.

Which study mode worked for you?

Saved in this browser onlySee all my progress →

See it move

VisuAlgo: Sorting: choose MER (merge sort).
VisuAlgo: Recursion tree: watch the call tree grow.

References

08 Divide & Conquer, Recurrences: Slides 3–4 (k-ary tree facts), 5 (D&C idea), 7–19 (merging step by step), 20–24 (MERGE and MERGE-SORT procedures), 25–29 (running time and recursion tree).
CLRS 4e §2.3 (designing algorithms: merge sort), Appendix B.5 (trees).

7 · Divide & conquer + merge sort

Everyday analogyCopy Anchor Link

Key ideasCopy Anchor Link

Common mistakesCopy Anchor Link

Mastery checkCopy Anchor Link

✅ Answer

See it moveCopy Anchor Link