Divide & Conquer

Divide and conquer is the oldest trick in the book, and stated plainly it sounds almost too obvious to be a technique: split the problem in half, solve each half, then stitch the answers together. The reason it is powerful is not the splitting, which is easy, but the stitching. The interesting divide-and-conquer algorithms are the ones where combining two solved halves is cheap, because that cheap combine step is what drives an O(n^2) problem down to O(n log n).

A quick warning about a bad example, because it is instructive. Finding the maximum of an array by splitting it in half, taking each half's max, and returning the larger is technically divide and conquer, but it buys you nothing: a plain left-to-right scan is already linear and far simpler. Divide and conquer only earns its keep when the combine step computes something the halves could not have known alone.

The archetype: merge sort

Merge sort is the pattern in its purest form. Split the array, sort each half recursively, and merge the two sorted halves into one. The merge is the whole point: two already-sorted lists fuse in a single linear pass, because you only ever compare their two front elements.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out.extend(left[i:]); out.extend(right[j:])
    return out

Each level of recursion touches all n elements once during merging, and there are log n levels of halving, which is exactly where O(n log n) comes from.

The array 5 2 4 1 split in half repeatedly down to single elements, then merged back up: 5 and 2 become 2 5, 4 and 1 become 1 4, and the two sorted halves merge into 1 2 4 5, with each of the log n levels touching all n elements during the merge.

In the wild: how far from sorted is this ranking?

Here is where the combine step turns into real leverage. Suppose you want to measure how much two rankings disagree, say a user's preferred order of items versus what your recommender served them. A natural measure is the number of inversions: pairs that are in the wrong relative order. Counting them by brute force is O(n^2), checking every pair. But inversions can be counted for free during a merge sort, because the merge already looks at exactly the pairs that cross the midline.

def sort_and_count(a):
    if len(a) <= 1:
        return a, 0
    mid = len(a) // 2
    left, cl = sort_and_count(a[:mid])
    right, cr = sort_and_count(a[mid:])
    out, i, j, cross = [], 0, 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
            cross += len(left) - i     # right[j] jumps ahead of every remaining left element
    out.extend(left[i:]); out.extend(right[j:])
    return out, cl + cr + cross

It is the same algorithm as merge sort; the only addition is one line that counts, each time an element from the right half is placed early, how many left-half elements it leapfrogged. That single accounting line, hung on the combine step, drops a quadratic count to O(n log n). And it is genuinely the same class of problem as sorting, because the crossing pairs the merge already inspects are the inversions. Measuring rank disagreement, a real task in recommender evaluation and rank correlation, comes out as a nearly free rider on a sort you already know how to do.

The trigger

A problem splits cleanly into independent halves whose answers combine cheaply, or you recognize a naive O(n^2) that keeps re-examining pairs. If you can describe an efficient way to merge two solved halves into the whole, divide and conquer is likely the frame, and the combine step is where the real design happens.

Where it shows up

  • Sorting: merge sort and quicksort are the canonical members.
  • Counting across a boundary: inversions, and other "how many pairs satisfy X" questions that ride on the merge.
  • Geometry and math: closest pair of points, fast matrix multiplication, the FFT, all built on divide, conquer, combine.

Where it bites

The two classic wounds are base cases and recursion depth. A missing or wrong base case sends the recursion off a cliff, and on very large inputs the call stack itself can overflow, so deep divide-and-conquer sometimes has to be flattened into an iterative form. Also watch the split: an unbalanced division, quicksort's worst case being the famous one, quietly degrades O(n log n) back to O(n^2).

When it is the wrong tool

If the subproblems overlap, solving the same smaller instance again and again, you are not looking at clean divide and conquer but at Dynamic Programming, which memoizes those shared subproblems instead of recomputing them; forcing plain recursion there is exponential. If the combine step is as expensive as solving the whole thing directly, the recursion adds overhead for no gain. And on small inputs the constant-factor cost of recursion and allocation loses to a simple loop, which is exactly why real sort implementations fall back to insertion sort below a threshold.

Its neighbors

Binary Search is divide and conquer stripped to its leanest, throwing away one half instead of solving both. Sorting-Based Patterns include its most famous members. And Dynamic Programming is the tool you graduate to the moment the subproblems start to overlap.

References