Divide and Conquer

The general pattern#

Divide and conquer is a strategy built from three explicit steps:

1. Divide — split the problem into smaller subproblems of the same type.
2. Conquer — solve each subproblem recursively (with some base case simple enough to solve directly, exactly as the recursion page described).
3. Combine — merge the subproblems' solutions into a solution for the original, larger problem.

Analogy: imagine grading a mountain of exam papers. Instead of grading all of them yourself, you split the stack among a few teaching assistants (divide), each of whom grades their smaller pile — recursively splitting further among sub-assistants if their pile is still too big (conquer) — and then all the individual grade sheets get collected and combined into one final gradebook (combine). Divide and conquer is recursion with this specific three-part shape, and critically, with a combine step that does real, necessary work.

Merge sort, revisited through this lens#

Merge sort, covered fully on the sorting algorithms page, is the textbook example of this pattern:

def merge_sort(arr):
    if len(arr) <= 1:              # base case
        return arr

    mid = len(arr) // 2
    left = merge_sort(arr[:mid])   # divide + conquer: recursively sort the left half
    right = merge_sort(arr[mid:])  # divide + conquer: recursively sort the right half

    return merge(left, right)      # combine: merge two sorted halves into one sorted whole

• Divide: split the array into two halves around the midpoint.
• Conquer: recursively merge_sort each half until hitting the base case.
• Combine: merge() — this is where the actual work of producing a sorted result happens. (Full code and a step-by-step trace for merge() are on the sorting algorithms page.)

Here's the general complexity recipe divide and conquer algorithms share, applied to merge sort specifically: at each level of the recursion tree, the combine step does O(n) total work summed across every call at that level (every element gets merged exactly once per level), and there are O(log n) levels total (since the array halves each time). O(log n) levels × O(n) work per level gives O(n log n) — derived from the shape of the recursion, not from memorizing the answer.

A second example: binary search as divide and conquer#

Binary search, from the searching algorithms page, fits the exact same three-step mold — just with an unusually light combine step:

def binary_search(arr, target, low=0, high=None):
    if high is None:
        high = len(arr) - 1
    if low > high:                       # base case: nothing left to search
        return -1

    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)   # divide: recurse into the right half only
    else:
        return binary_search(arr, target, low, mid - 1)    # divide: recurse into the left half only

• Divide: compare the target to the middle element to determine which half could possibly contain it.
• Conquer: recursively search only that half — the other half is discarded entirely, with no need to explore it at all.
• Combine: trivial. There's nothing to merge, because only one half was ever explored in the first place.

That difference in the combine step is exactly why binary search and merge sort end up with different complexities despite both recursing O(log n) levels deep. Merge sort must process both halves and then do O(n) work merging them back together at every level, giving O(n log n) overall. Binary search discards one entire half at each step and does O(1) work at each level (just one comparison), giving O(log n) overall — a whole factor of n cheaper, purely because its combine step has nothing left to do.

How this differs from dynamic programming#

Divide and conquer works best when the subproblems it creates are genuinely independent — solving the left half of an array never needs anything computed while solving the right half, so there's no reason to remember earlier work. But some problems split into subproblems that overlap — the naive recursive Fibonacci from the recursion page is the clearest example, where computing fib(4) and fib(3) both require solving fib(2), redundantly, from scratch, every single time.

When subproblems are independent, straightforward divide and conquer (as seen in both examples above) is the right tool. When subproblems overlap heavily, that redundant recomputation becomes genuinely wasteful — exponentially so, in Fibonacci's case — and a different strategy is called for: one that deliberately notices repeated subproblems and caches their answers instead of recomputing them. That strategy is dynamic programming, the subject of the next page, and it builds directly on the memoization idea the recursion page already introduced.

Common mistakes#

• Assuming any recursive algorithm is "divide and conquer." The pattern specifically requires splitting into multiple subproblems and a meaningful combine step — plain linear recursion like factorial only ever produces one subproblem per call, so it doesn't fit this shape.
• Forgetting the combine step's cost when estimating overall complexity. It's easy to account only for the recursive calls and forget that merging results back together (like merge sort's O(n) merge, repeated at every level) contributes real, sometimes dominant, time.
• Applying divide and conquer to a problem with heavily overlapping subproblems without memoization, causing exponential blowup exactly like naive Fibonacci — a strong signal to reach for dynamic programming instead.
• Assuming divide and conquer always splits evenly in half. Some divide and conquer algorithms split unevenly — quicksort's partition step is a divide-and-conquer split too, and it's precisely that split's potential unevenness (an unlucky pivot) that causes quicksort's O(n²) worst case.