the divide-conquer-combine template

Imagine you must alphabetize a huge box of paper forms by hand. Doing it all at once is overwhelming, so you split the box into two halves, hand each half to a friend, and ask them to sort their half the same way. When both halves come back sorted, you only have to interleave them into one sorted pile. That instinct — cut the work into pieces, solve the pieces, then stitch the answers together — is the divide-and-conquer template, the most common way to design fast recursive algorithms.

Precisely, the template has three steps. DIVIDE: split the problem of size n into a (usually 2) subproblems, each of size about n/b (usually n/2). CONQUER: solve each subproblem by calling the same procedure recursively; the recursion bottoms out at a base case small enough to solve directly (for example, an array of one element is already sorted). COMBINE: take the subproblem answers and assemble the answer to the original problem. A tiny trace for merge sort on [3,1,2,4]: divide into [3,1] and [2,4]; conquer recursively to get [1,3] and [2,4]; combine by merging to get [1,2,3,4]. The cost is captured by a recurrence such as T(n) = 2 T(n/2) + O(n), where the O(n) is the combine work.

Divide and conquer matters because, when the combine step is cheap, splitting in half drives the running time down to O(n log n) or better, beating the O(n^2) of many direct methods. It powers merge sort, quicksort, binary search, fast multiplication, the FFT, and linear-time selection. The one rule you must respect: the subproblems should be genuinely independent — solving one must not depend on having already solved another. When they overlap and you would re-solve the same subproblem many times, divide and conquer alone is wasteful and you want dynamic programming instead.