A three step rhythm
Divide and conquer is a general strategy built from three repeating steps that apply to a shrinking problem.
- Divide the problem into smaller subproblems of the same kind.
- Conquer each subproblem by solving it recursively, stopping at a small base case.
- Combine the subsolutions into an answer for the original.
The power comes from the subproblems being the same shape as the original, so one routine handles every level.
Classic examples
- Merge sort splits a list in half, sorts each half, and merges the sorted halves.
- Binary search halves the search range and recurses into the side that can hold the target.
- Quicksort partitions around a pivot and recurses on each side.
Why it is efficient
Each level of recursion shrinks the problem, often halving it, so the number of levels stays small. The combine step then knits results together. The cost is captured by a recurrence that the master theorem can solve.
The combine step matters
A cheap combine keeps the whole algorithm efficient, while an expensive merge can dominate and erase the benefit of splitting.
Key idea
Divide and conquer splits a problem into same shaped subproblems, solves them recursively to a base case, and combines the results, with overall efficiency hinging on cheap division and merging.