Divide & Conquer

The 10-second versionCopy Anchor Link

Divide and conquer is a way to solve a problem by splitting it into smaller copies of itself, solving those recursively, and then combining their answers into the answer for the whole. The split usually gets all the attention, but the real story is the combine step — it decides the whole complexity. Split a problem into two halves and merge the results in linear time, and you get Θ(n log n); split it into three pieces and glue them back in linear time, and the exponent itself changes. Same idea, wildly different bill.

Why this existedCopy Anchor Link

For the first decades of computing, "sort this data" meant comparing things one pair at a time, and the honest cost of that was O(n²): for n = 10,000 you were signing up for a hundred million comparisons. On the machines of the 1940s that was not a metaphor — it was hours.

• 1945 — John von Neumann, while drafting the report that would define the stored- program computer (EDVAC), describes a merge sort: split the list, sort each half recursively, then merge. It's the earliest recorded divide-and-conquer sorting algorithm, and it drops the cost to Θ(n log n).
• 1946 — John Mauchly sketches the first binary search, which throws away half its remaining range on every comparison. The two ideas look different on the surface and are the same move underneath: shrink the problem, never re-examine what you've discarded.
• 1960 — Anatoly Karatsuba, a 23-year-old student, hears Andrey Kolmogorov conjecture that multiplying two n-digit numbers needs n² single-digit operations — that it's impossible to do better. Within a week Karatsuba finds a divide-and-conquer trick that beats it, and at n^1.585 the field's most famous "obviously optimal" wall falls. Everyone thought n² was the floor. It wasn't.
• 1965 — Cooley and Tukey publish the Fast Fourier Transform, another split-and- combine that turns O(n²) signal work into O(n log n).
• 1980 — Bentley, Haken, and Saxe give the recurring-complexity analysis a name: the master theorem.

Why it mattered then: it was the first general principle that let people design fast algorithms instead of just discovering them. You didn't need a clever trick for your specific problem — you needed to find a way to halve it.

Inside the inventor's headCopy Anchor Link

Start with von Neumann staring at an unsorted pile. His instinct is the natural one: to sort the whole thing is hard, but sorting one element is trivial, and merging two already sorted lists is easy — you just walk both from the left, always taking the smaller front item.

Watch the two thoughts collide:

The pivot isn't "split." Splitting is easy — you can always chop a list. The pivot is realizing the combine step can be made nearly free: merging two sorted runs costs one comparison per output element, Θ(n). Without a cheap combine, halving buys you nothing.

That's exactly the lesson Karatsuba hit fifteen years later, on a problem nobody expected it on. Grade-school multiplication of two 2-digit numbers needs four single-digit products:

     a b        (a·10 + b)
   × c d      × (c·10 + d)
   -----      -------------------------
   ac bd      = ac·100 + (ad + bc)·10 + bd

Four multiplications: ac, ad, bc, bd. His first instinct was the obvious one — there is no way around four. Then this:

Three multiplications, not four — and the recurrence T(n) = 3·T(n/2) + Θ(n) solves to Θ(n^1.585), beating the wall. Same split as before; a smarter combine changed the answer.

// Grade-school: one multiply, but carries grow with O(n^2) digit workconst mulNaive = (x, y) => x * y;// Karatsuba: 3 recursive products per level instead of 4function karatsuba(x, y) {  if (x < 10 || y < 10) return x * y;  let half = 1;  while (half * 10 <= x || half * 10 <= y) half *= 10;  const xl = Math.floor(x / half), xr = x % half;  const yl = Math.floor(y / half), yr = y % half;  const p1 = karatsuba(xl, yl);  const p2 = karatsuba(xr, yr);  const p3 = karatsuba(xl + xr, yl + yr);  // the clever combine  return p1 * half * half + (p3 - p1 - p2) * half + p2;}

The final approachCopy Anchor Link

The shape of every divide-and-conquer algorithmCopy Anchor Link

Three steps, always the same three: divide, conquer, combine. The first two are mechanical once you've picked a split; the third is where correctness and speed are won or lost.

The invariant that makes it correctCopy Anchor Link

Divide and conquer leans on strong induction on the input size:

• Claim: a recursive call on a subproblem of size k returns the correct answer for that subproblem.
• Base case: the smallest inputs are solved directly, and that direct solve is correct.
• Inductive step: assuming the sub-calls are correct, the combine step turns correct sub-answers into a correct whole answer.

For merge sort specifically the combine invariant is: after processing k elements, the output holds the k smallest elements of the two inputs, in sorted order. Walk both fronts, take the smaller, advance — and that invariant holds after every single step.

Counting the work: the master theoremCopy Anchor Link

The cost of a divide-and-conquer algorithm is a recurrence — an equation that defines the cost in terms of itself:

T(n) = a · T(n/b) + f(n)

a subproblems, each of size n/b, plus f(n) work to divide and combine. The master theorem tells you the answer, and — this is the point — it tells you which part dominates:

Merge sort: a = 2, b = 2, so log_b a = 1, and the combine is f(n) = Θ(n). That's a tie — case 2 — so T(n) = Θ(n log n). Karatsuba: a = 3, b = 2, f(n) = Θ(n), and log_2 3 ≈ 1.585 beats 1 — case 1 — so T(n) = Θ(n^1.585).

A worked traceCopy Anchor Link

Sort [38, 27, 43, 3]. Down the recursion we go, halving until each piece is a single element; then up, merging:

The tree has log₂ n levels, and each level does Θ(n) total merging work. That product — n work across log n levels — is precisely Θ(n log n).

The full implementationCopy Anchor Link

function mergeSort(a) {  if (a.length <= 1) return a;               // base case  const mid = a.length >> 1;                 // divide  const left = mergeSort(a.slice(0, mid));   // conquer left  const right = mergeSort(a.slice(mid));     // conquer right  return merge(left, right);                 // combine}function merge(left, right) {  const out = [];  let i = 0, j = 0;  while (i < left.length && j < right.length)    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;}

ComplexityCopy Anchor Link

Where you meet it todayCopy Anchor Link

• Sorting, everywhere. std::sort's introsort, sort.Slice in Go, and Python's Timsort are all descendant of "split and merge." Mergesort's stability and predictable n log n are why it shows up in database sort operators.
• Big-number math. GMP and every language's bignum library uses Karatsuba (and its successors, Toom-Cook and FFT) to multiply. Your BigInt literally earns its speed from the 1960 discovery that n² wasn't optimal.
• Signal processing & media. The FFT — Cooley-Tukey, 1965 — is divide-and-conquer on polynomial evaluation, and it's the engine behind audio codecs, JPEG/MP3, and radar.
• Distributed systems. MapReduce is the same skeleton at cluster scale: divide the data, conquer on many machines, combine the partial results.

// Even/odd decomposition: the two halves the FFT recurses on.const splitEvenOdd = (p) => {  const even = [], odd = [];  for (let i = 0; i < p.length; i += 2) {    even.push(p[i]);    odd.push(p[i + 1]);  }  return { even, odd };};

RecapCopy Anchor Link

• Divide and conquer is divide → conquer → combine, and every part is the same problem, smaller.
• The combine step decides the complexity, not the split. Cheap merge gives n log n / n^1.585; expensive merge gives the naive answer back.
• The master theorem reads a recurrence T(n) = a·T(n/b) + f(n) and tells you whether the leaves, the balanced middle, or the root dominates.
• Correctness is strong induction: base case correct + combine preserves correctness.
• Karatsuba is the cautionary tale: "obviously optimal" is a hypothesis, not a proof.

Next up: Greedy Algorithms — when you can skip the combine-and-check entirely and just grab the best local choice.