Divide and conquer

Suppose a teacher drops a heavy box of 1000 unsorted exam scripts on your desk and asks for the single highest mark. On your own that's a slog. But you're not on your own — there are thirty of you. So you don't tackle the box; you split it. Half to the left of the room, half to the right. Each half splits again, and again, until every person holds just a handful of scripts they can eyeball in seconds. Then the answers travel back the other way: each pair of people compares their two best marks and passes the winner upward, pair by pair, until one champion mark emerges at the front. A mountain of work has melted into a few quick rounds.

That is divide and conquer — one of the most powerful problem-solving strategies in all of computing. It is a pattern, not a single algorithm, and once you can see it you'll spot it everywhere: in binary search, in merge sort, and in dozens of the fastest algorithms ever written. This page is about the shape they all share.

The three moves

A divide-and-conquer algorithm always makes the same three moves. Learn these three words and you have the whole idea:

Divide — break the problem into two or more smaller sub-problems that are the same kind of problem as the original, just tinier.
Conquer — solve each sub-problem. Because a sub-problem is the same shape as the whole, you usually solve it the same way: by recursion. The splitting keeps going until a piece is so small the answer is obvious — that's the base case.
Combine — glue the sub-answers back together into the answer for the whole problem.

The three moves map cleanly onto a recursive function: the divide chooses how to split, the conquer is the recursive call (or the base case, at the bottom), and the combine is whatever you do with the values those calls hand back. Watch one problem — finding the biggest number in a list — travel down as it divides and back up as it combines:

Read the top half downwards: the list halves until each piece is a single number, whose maximum is just itself (the base case). Then read the bottom half: each pair of answers is combined by keeping the larger, level by level, until one number — the overall maximum — pops out at the top.

Maximum of a list, by splitting in half

Let's build that tree in code. Finding the biggest number is easy with a loop, but doing it by divide and conquer shows the pattern in its purest form. To find the max of a slice of the list:

Divide: cut the slice into a left half and a right half.
Conquer: find the max of each half (by calling ourselves). A slice of one item is the base case — its max is that item.
Combine: the answer is the larger of the two halves' maxima.

Press Run and read the log — you'll see tiny slices resolve first, then combine upward:

Every call does a trivial amount of work — one Math.max — yet together they find the answer. That's the divide-and-conquer bargain: no single step is clever, but the structure of splitting and recombining does the heavy lifting. Notice the base case (a slice of length one) and that each call recurses on a strictly smaller slice, so the splitting is guaranteed to stop.

Why halving buys a logarithm

Divide and conquer isn't just tidy — when the pieces are genuinely halved each time, it makes algorithms dramatically faster. The reason is a number that appears again and again: \log_2 n, the number of times you can halve n before you reach 1.

n \to \tfrac{n}{2} \to \tfrac{n}{4} \to \cdots \to 1 \qquad\text{takes about } \log_2 n \text{ halvings.}

Halve 8 and you get 8 \to 4 \to 2 \to 1: three halvings, and indeed \log_2 8 = 3. Halve a thousand and it takes only about ten; a million, only about twenty. The chart below shows how gently \log_2 n (the depth of the splitting) grows next to n itself:

This single fact powers the two algorithms you've already met:

Binary search divides the list in half and throws one half away, so it only ever walks one path down the tree — about \log_2 n comparisons instead of n.
Merge sort divides the list in half, sorts both halves, and combines them with a merge that costs about n per level. With \log_2 n levels, that's about n \log_2 n — far below the n^2 of the simple sorts.

Whether you keep one half (search) or both (sort), the depth of the divide-and-conquer tree is the logarithm — and that depth is where the speed-up is hiding.

Repeated squaring: raising a number to a power, fast

Here's a fresh example where divide and conquer turns a slow job into a lightning-fast one. To compute x^n the obvious way, you multiply x by itself n times — that's n multiplications. Divide and conquer does far better by splitting the exponent in half:

x^n = \left(x^{n/2}\right)^2 \quad(n \text{ even}) \qquad\qquad x^n = x \cdot \left(x^{(n-1)/2}\right)^2 \quad(n \text{ odd})

Compute x^{n/2} just once, then square it — one multiplication instead of doubling the work. Because the exponent halves every step, only about \log_2 n multiplications are needed. Run it and compare the counts:

let multiplications: number = 0; function power(x: number, n: number): number { if (n === 0) return 1; // base case: anything^0 = 1 const half: number = power(x, Math.floor(n / 2)); // conquer: x^(n/2), computed ONCE multiplications++; const squared: number = half * half; // combine: square it if (n % 2 === 1) { // odd n needs one extra x multiplications++; return squared * x; } return squared; } console.log("3^13 =", power(3, 13)); console.log("multiplications used:", multiplications, "(naive way would use 13)"); console.log("2^30 =", power(2, 30), "in", "~30 halvings vs 30 multiplies — try bigger n!");

The key move is reusing half for both factors instead of recomputing it — the sub-problem is solved once and its result combined with itself. This trick (called exponentiation by squaring) is exactly how computers raise huge numbers to huge powers inside cryptography, where exponents can have hundreds of digits and the naive method would never finish.

Not quite — the sub-problems must be the same kind of problem as the original, and (usually) independent of each other, so they can be solved separately and then combined. Merge sort's two halves don't need to talk to each other; neither do the two halves of a maximum search. That independence is what lets the recursion fan out cleanly.

When sub-problems overlap — the same little sub-problem gets solved over and over — plain divide and conquer becomes wasteful. That's exactly what happens with naive Fibonacci, and the fix has its own name: dynamic programming, which remembers sub-answers instead of recomputing them. A story for another page — but a good reminder that "split it up" is only half the pattern.

A divide-and-conquer algorithm on a problem of size n does three things:

Divide the problem into a sub-problems, each of size about n/b (for merge sort, two halves: a=2, b=2).
Conquer each sub-problem recursively, stopping at a base case small enough to answer directly.
Combine the sub-answers into the whole answer; the cost of combining, summed over all \log_b n levels, sets the overall running time.

Divide and conquer is recursion, so it inherits recursion's number-one bug: a missing or unreachable base case. If your splitting never bottoms out at a piece small enough to answer directly, the calls pile up forever and the program dies with a stack overflow. Always write the base case first — "a slice of one item", "an empty list", "an exponent of zero" — and make sure every recursive call is on something strictly smaller, so it's always heading toward that base case.

The subtler trap is thinking the split alone is the algorithm. It isn't — the combine step is where the real answer is assembled, and it has to be correct and cheap. Merge sort would be pointless if merging two sorted halves were slow; binary search works because "combining" is free (you just discard a half). Chopping a problem up buys you nothing unless (a) the pieces are genuinely smaller, (b) they're independent enough to solve on their own, and (c) stitching the answers together is cheaper than solving the whole thing directly. Miss any of those and all the splitting in the world won't make you faster.