Divide & Conquer

The shape

Three steps: divide the input into subproblems, conquer them recursively, combine the results. Merge sort and binary search are the archetypes:

def merge_sort(a):
    if len(a) <= 1: return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    return merge(left, right)        # the "combine" step does the real work

The combine step is where problems hide

Sorting is often incidental — the merge counts or computes the real answer:

• Count of Smaller Numbers After Self / Reverse Pairs — count cross-pairs while merging two sorted halves (each right element smaller than left ones contributes).
• Maximum Subarray (D&C form) — the best subarray lies in the left half, the right half, or crosses the middle (compute the crossing max in O(n)).
• Construct tree from traversals — the root splits the arrays into left/right subtrees.
• Closest pair of points — split by x, solve halves, combine across the dividing strip.

The pattern: a problem becomes easy once results for the halves are known and you handle the cross-boundary case in combine.

Quickselect — D&C that recurses into one side

To find the kth smallest without full sorting, partition around a pivot (like quicksort) and recurse only into the side containing k — O(n) average, O(n²) worst (mitigate with a random pivot or median-of-medians):

def quickselect(a, k):               # k-th smallest (0-indexed)
    pivot = a[len(a)//2]
    lo  = [x for x in a if x < pivot]
    eq  = [x for x in a if x == pivot]
    hi  = [x for x in a if x > pivot]
    if k < len(lo):           return quickselect(lo, k)
    if k < len(lo) + len(eq): return pivot
    return quickselect(hi, k - len(lo) - len(eq))

The fastest average-case answer to “Kth Largest Element” / “Top-K” when you can mutate the array.

Cost: the Master Theorem (intuition)

Split into a subproblems of size n/b, combine in O(n^d):

• a < b^d → combine dominates → O(n^d).
• a = b^d → O(n^d log n) (merge sort: 2 halves, linear merge → n log n).
• a > b^d → leaves dominate → O(n^{log_b a}) (e.g. naive recursive Fibonacci, Karatsuba multiplication O(n^{1.585})).

This lets you read a recurrence’s complexity at a glance.

Relation to other patterns

• Binary search is divide-and-conquer that throws away one half each step (see that primer).
• Quicksort / merge sort are D&C sorts (see the sorting primer).
• When subproblems overlap (the same one recurs), plain D&C recomputes them — switch to DP (memoization turns exponential D&C into polynomial). Reach for plain D&C only when subproblems are independent.

Pitfalls

• Forgetting the cross-boundary case in combine (the max-subarray middle, the merge-count pairs).
• Unbalanced splits — a bad quickselect/quicksort pivot degrades to O(n²); randomize.
• Slicing cost — in Python, a[:mid] copies O(n); pass indices for in-place variants when it matters.

Choosing in an interview

• Independent halves + a meaningful merge → divide & conquer (state the combine step).
• Kth element / top-K, can mutate → quickselect (O(n) average).
• Overlapping subproblems → DP instead.
• Recurrence cost → Master Theorem.