Divide and Conquer: Split, Solve, Combine

Divide and conquer is a way of designing an algorithm in three steps: divide the problem into smaller problems of the same kind, conquer each one by calling the same algorithm on it, and combine their answers into the answer for the whole. This card covers the three steps, the base case that stops the calls, and where an algorithm's work can sit among the steps.

The conquer step is a recursive call, a function calling itself on a smaller input. Each call divides again, so the problems keep shrinking until one is small enough to answer directly, usually a single item. That smallest problem is the base case, and it is where the calls stop and the answers start coming back up.

Finding the largest value in an array is the plainest instance. To find the largest of 7 3 9 1 6 8 2 5, divide the array at its middle into 7 3 9 1 and 6 8 2 5, find the largest of each half by the same method, and combine by keeping the larger of the two answers. A half of one item is the base case: its largest value is that item. The tree below shows every call an instrumented run made, each named by the part of the array it was given, with the value it returned.

The run made 15 calls: one for the whole array, two for its halves, four for the quarters and eight for the single items, which return themselves. Every call above the leaves did one comparison to combine, 7 in all, which is the n − 1 comparisons a plain loop would make. Divide and conquer does not make finding the largest any cheaper. It is the clearest instance because its divide and combine steps are each a single operation, so nothing hides the shape.

Where an algorithm does its real work differs from one algorithm to the next, and it is the first thing to look for when you meet one. Two sorts later in this subject put it at opposite ends.

Merge sort, a later topic, divides without looking at the items and does its linear work in the combine. Quicksort, also a later topic, does the opposite: partitioning puts every item on the correct side of the pivot before the recursive calls, so once both parts are sorted there is nothing left to join.

A national election count works the same way. Each region counts its own ballots, perhaps by splitting the work among its districts, and the national total is the regional totals added up. The analogy breaks on timing: the regions count at the same time, but a program running on one thread solves the parts one after another, so splitting a problem saves nothing by itself. Any saving has to come from the combine being cheaper than solving the whole problem directly, which is how merge sort beats the elementary sorts.

Not every recursive algorithm is divide and conquer. An insertion sort written recursively sorts the first n − 1 items and then inserts the last one: the problem shrinks by one item per call, so the calls run n deep and the cost stays O(n²). Divide and conquer cuts the size by a fraction, usually a half, so the depth is about log₂ n. Binary search sits on the border: it makes one call on half the range, which some books call decrease and conquer, but its cost is written and solved in the same form, so this topic counts it.

Naming the three steps is what makes the cost readable. Count the calls a step makes and the size of each, add the work done in the divide and the combine, and you have the recurrence the rest of this topic solves.