Divide and Conquer

By Victor Arce

Some of the fastest algorithms share one move: when a problem is too big, split it into smaller copies of itself, solve those, and stitch the answers back together. That's divide and conquer, and it's the reason merge sort, quicksort, binary search and the FFT all run so well.

Step through the tree below. The whole problem sits at the top; each level halves the pieces until they're trivial, then the solutions combine back up.

The three moves

Every divide-and-conquer algorithm is built from the same three steps:

1. DivideDivide: split the problem into smaller subproblems — here, halves of the array. — split the input into smaller subproblems (usually two halves).
2. Conquer — solve each subproblem the same way, recursively, until a piece is small enough to answer outright (the base case, size 1 here).
3. Combine — merge the subproblem answers into the answer for the whole.

Merge sort is the textbook example: divide the array in half, sort each half, then merge the two sorted halves. Quicksort divides by partitioning around a pivot; binary search divides by throwing away the half that can't contain the target.

Why it costs O(n log n)

The tree makes the cost visible. Halving from n down to 1 takes log₂n levels. At every level the pieces together still hold all n items, so the combine work across a level totals O(n)O(n) — linear time: the work grows in direct proportion to the number of items n.. Multiply:

log₂n levels × O(n) per level = O(n log n)O(n log n) — linearithmic time: n times log n; the best worst-case for comparison sorts..

That's the same linearithmic class from the Big-O primer — and it's a genuine jump down from the O(n²)O(n²) — quadratic time: the work grows with the square of the number of items. of the simple sorts. The win comes from the shape of the recursion: shallow (only log n deep) but doing modest work at each level.

Back to Foundations