The D&C Template

Every divide-and-conquer algorithm fits the same skeleton. Once you can write it from memory, the work on any new problem is filling in three blanks:

1. How to split the input.
2. What the base case looks like.
3. How to combine the subanswers.

That’s it. The recurrence — and therefore the runtime — falls out of those three choices automatically.

The skeleton

def solve(input):
    if input is small enough:
        return brute_force(input)              # base case

    parts = split(input)                        # divide

    sub_answers = [solve(p) for p in parts]    # conquer

    return combine(sub_answers, input)          # combine

Four lines. Most D&C problems hide their interesting work in the combine step.

The four canonical recurrence shapes

You’ll see these four over and over. Memorize them.

Shape 1: T(n) = T(n / 2) + O(1) → O(log n)

One recursive call, half the size, constant combine. Binary search. Fast exponentiation (pow(x, n) viewed by halving n).

def binary_search(arr, target, lo, hi):
    if lo > hi: return -1
    mid = (lo + hi) // 2
    if arr[mid] == target: return mid
    if arr[mid] < target: return binary_search(arr, target, mid + 1, hi)
    else:                 return binary_search(arr, target, lo, mid - 1)

The trick: one of the two halves is discarded entirely. Each level of recursion halves the problem; there are log n levels.

Shape 2: T(n) = T(n / 2) + O(n) → O(n)

One recursive call, half the size, linear combine. Quickselect (when the pivot is good). Counting inversions in a half (with appropriate setup).

def quickselect(nums, k, lo, hi):
    if lo == hi: return nums[lo]
    p = partition(nums, lo, hi)                # O(n) combine
    if p == k: return nums[p]
    if k < p:  return quickselect(nums, k, lo, p - 1)
    else:      return quickselect(nums, k, p + 1, hi)

The combine cost dominates: O(n) + O(n/2) + O(n/4) + ... = O(2n) = O(n).

Shape 3: T(n) = 2 T(n / 2) + O(1) → O(n)

Two recursive calls, half-size each, constant combine. Counting nodes in a balanced binary tree. Computing the maximum of an array.

def tree_size(node):
    if not node: return 0
    return 1 + tree_size(node.left) + tree_size(node.right)

The recursion tree has O(n) leaves; each does constant work. Total O(n).

Shape 4: T(n) = 2 T(n / 2) + O(n) → O(n log n)

Two recursive calls, half-size each, linear combine. Merge sort. D&C Maximum Subarray. Closest Pair of Points. Inversion counting via merge sort.

def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)                  # O(n) combine

The most common D&C shape in interviews. O(n log n) time, log n recursion depth.

The recipe — putting it all together

When you see a new problem and suspect D&C, run this:

If you can answer all five, the code writes itself.

A worked example: counting inversions via merge sort

An inversion is a pair (i, j) with i < j and nums[i] > nums[j]. Count the total number of inversions in nums.

The brute force is O(n²) — check every pair. The D&C trick: merge sort, with an inversion counter added to the merge step.

• Split: halve the array.
• Conquer: recursively count inversions in each half, returning the sorted half.
• Combine: count cross-inversions (pairs with i in left, j in right) while merging. When taking right[j] before left[i], every remaining element in left forms an inversion with right[j].

def count_inversions(nums):
    def merge_count(arr):
        if len(arr) <= 1: return arr, 0
        mid = len(arr) // 2
        left,  c1 = merge_count(arr[:mid])
        right, c2 = merge_count(arr[mid:])
        merged, c3 = [], 0
        i = j = 0
        while i < len(left) and j < len(right):
            if left[i] <= right[j]:
                merged.append(left[i]); i += 1
            else:
                merged.append(right[j]); j += 1
                c3 += len(left) - i                       # every remaining left elt > right[j]
        merged.extend(left[i:]); merged.extend(right[j:])
        return merged, c1 + c2 + c3
    _, total = merge_count(nums)
    return total

Recurrence: T(n) = 2 T(n / 2) + O(n) → O(n log n). Same recurrence as plain merge sort; the inversion count is “free” in the combine step.

This pattern — piggyback extra accounting onto the merge step — is the engine behind a whole family of inversion / pair-counting problems.

The four shapes one more time

Plus two notable cousins:

Common bugs the template helps you avoid

• Forgetting the base case → infinite recursion / stack overflow.
• Wrong base case (n == 0 vs n == 1) → off-by-one in the final answer.
• Including the dividing line in both halves → cubic blowup.
• Forgetting the combine step → returns the wrong half’s answer.
• Underestimating the combine cost → wrong runtime claim.

Quick check

Next: the Master Theorem — the formula that handles 90% of D&C runtime analyses in one line.