Lesson 17
Merge Sort: Divide, Conquer, Combine
Guaranteed O(n log n) by splitting until trivial, then zipping back together.
01Why it matters & the intuition
Merge sort is the canonical divide-and-conquer algorithm and the default stable sort in many languages. The merge step alone solves a whole family of interview problems.
Think of it like…
Two friends each sort half a stack of exam papers. You then merge the two sorted stacks by repeatedly taking whichever top paper has the lower roll number. Sorting each half is the same problem — so each friend splits theirs too.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- comparing / current
- moving / removing
- done / found / visited
- pivot / min / root
03Key ideas
Divide
Split the array in half until each piece has 0 or 1 elements — trivially sorted.
Merge
Walk two sorted arrays with two pointers, always taking the smaller head. O(n) per level.
log n levels
Halving gives log₂ n levels; each level does O(n) merging work: O(n log n) total, in every case.
Trade-off
Merge sort needs O(n) extra space for merging, but it is stable and its performance never degrades.
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
function mergeSort(a: number[]): number[] {
if (a.length <= 1) return a;
const mid = Math.floor(a.length / 2);
return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}
function merge(left: number[], right: number[]): number[] {
const out: number[] = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
// <= keeps the sort stable
out.push(left[i] <= right[j] ? left[i++] : right[j++]);
}
while (i < left.length) out.push(left[i++]);
while (j < right.length) out.push(right[j++]);
return out;
}05Complexity
| Operation | Time | Space |
|---|---|---|
| Time (best / avg / worst) | O(n log n) | — |
| Extra space | — | O(n) |
| Stable | yes | — |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Merge two sorted arrays
Write merge_sorted(a, b) that merges two ascending arrays into one ascending array in O(a + b). No .sort().