Divide & Conquer

Divide and conquer breaks a problem into independent subproblems of the same kind, solves those recursively, and combines the results. The leverage comes from the subproblems being independent — no shared state, no communication — which is also what makes the pattern parallelise so naturally.

Three steps, always: divide, conquer, combine. Which step does the real work varies, and that variation is what distinguishes mergesort from quicksort.

Core Concepts

Algorithm	Divide	Conquer	Combine
Mergesort	Trivial — split in half	Sort each half	Merge — $O(n)$
Quicksort	Partition — $O(n)$	Sort each side	Trivial — nothing to do
Binary search	Compare to the midpoint	One side only	Trivial
Karatsuba multiplication	Split the digits	3 subproducts	Shift and add
Strassen's matrix multiply	Split into quadrants	7 subproducts	Add submatrices

Mergesort and quicksort are exact mirrors: one does its work combining, the other dividing. Binary search is the degenerate case that discards a subproblem instead of solving it, which is why it is logarithmic rather than linear.

Mechanism

Python

def divide_and_conquer(problem):
    if is_small_enough(problem):
        return solve_directly(problem)          # base case
    subproblems = divide(problem)
    results = [divide_and_conquer(p) for p in subproblems]
    return combine(results)

C++

// doc:no-run
// illustrative skeleton — Result/Problem are placeholders, not real types
Result divide_and_conquer(const Problem& problem) {
    if (is_small_enough(problem))
        return solve_directly(problem);          // base case
    std::vector<Result> results;
    for (const auto& p : divide(problem))
        results.push_back(divide_and_conquer(p));
    return combine(results);
}

Traced on the shared sorting input [5, 1, 8, 3, 9, 2, 7, 4], mergesort's recursion tree — divide splits every array in half down to single elements, then combine merges pairs back up in sorted order, level by level:

level 0 (divide)     [5,1,8,3,9,2,7,4]
level 1 (divide)     [5,1,8,3]              [9,2,7,4]
level 2 (divide)     [5,1]    [8,3]         [9,2]    [7,4]
level 3 (base case)  [5][1]   [8][3]        [9][2]   [7][4]

level 2 (combine)    [1,5]    [3,8]         [2,9]    [4,7]
level 1 (combine)    [1,3,5,8]              [2,4,7,9]
level 0 (combine)    [1,2,3,4,5,7,8,9]

Three divide levels turn 8 elements into 8 singletons (log2(8) = 3), and each of the 4 combine steps does $O(n)$ work summed across its level — 3 levels of $O(n)$ merging is the $Θ(n \log n)$ the Master Theorem predicts for this recurrence; see below for the general method.

Reading the recurrence

Every divide-and-conquer algorithm has a recurrence of the shape $T(n) = a \cdot T(n/b) + f(n)$ — a subproblems, each of size n/b, plus f(n) work to divide and combine. Mergesort's is $T(n) = 2T(n/2) + O(n)$, which the tree above traces directly: 2 subproblems per level, halving in size, with $O(n)$ total merge work at every level. Working out the closed-form result for an arbitrary recurrence — and the three cases that decide whether the leaves, every level, or the root dominates — is not repeated here; see Recurrences & the Master Theorem for the full method and worked examples including Karatsuba and Strassen's, both of which win by reducing a rather than shrinking the subproblem.

Practical Usage

Python

# Maximum subarray, divide and conquer — O(n log n)
# (Kadane's algorithm solves this in O(n); this version shows the pattern.)
def max_subarray(a, lo, hi):
    if lo == hi:
        return a[lo]
    mid = (lo + hi) // 2
    left = max_subarray(a, lo, mid)             # entirely in the left half
    right = max_subarray(a, mid + 1, hi)        # entirely in the right half

    # The third case: crossing the midpoint. This is the "combine" step.
    best_left, total = float("-inf"), 0
    for i in range(mid, lo - 1, -1):
        total += a[i]
        best_left = max(best_left, total)
    best_right, total = float("-inf"), 0
    for i in range(mid + 1, hi + 1):
        total += a[i]
        best_right = max(best_right, total)

    return max(left, right, best_left + best_right)


A = [5, 1, 8, 3, 9, 2, 7, 4]
assert max_subarray(A, 0, len(A) - 1) == 39        # the whole array — no negative numbers to avoid

C++

#include <algorithm>
#include <limits>
#include <vector>

// Maximum subarray, divide and conquer — O(n log n)
// (Kadane's algorithm solves this in O(n); this version shows the pattern.)
int max_subarray(const std::vector<int>& a, int lo, int hi) {
    if (lo == hi) return a[lo];
    int mid = lo + (hi - lo) / 2;
    int left  = max_subarray(a, lo, mid);           // entirely in the left half
    int right = max_subarray(a, mid + 1, hi);       // entirely in the right half

    // The third case: crossing the midpoint. This is the "combine" step.
    int best_left = std::numeric_limits<int>::min(), total = 0;
    for (int i = mid; i >= lo; --i) {
        total += a[i];
        best_left = std::max(best_left, total);
    }
    int best_right = std::numeric_limits<int>::min();
    total = 0;
    for (int i = mid + 1; i <= hi; ++i) {
        total += a[i];
        best_right = std::max(best_right, total);
    }

    return std::max({left, right, best_left + best_right});
}

Where the pattern shows up beyond sorting:

• Parallel processing. MapReduce is divide and conquer with the subproblems distributed across machines; the independence of subproblems is exactly what makes the distribution safe.
• Fast Fourier Transform — $O(n \log n)$ instead of $O(n^2)$, by splitting into even and odd indices.
• Closest pair of points — $O(n \log n)$ instead of the $O(n^2)$ of checking all pairs.
• Quickselect — quicksort that recurses into only one side, giving $O(n)$ average for the k-th smallest element.
• Binary search and every balanced-tree operation.

Edge Cases & Pitfalls

Divide and conquer requires independent subproblems

When subproblems overlap — the same sub-computation appearing in several branches — plain recursion recomputes it exponentially often. Naive Fibonacci is the standard demonstration: fib(n-1) and fib(n-2) share almost all their work, and the runtime is $O(2^n)$ for an $O(n)$ problem.

Overlapping subproblems mean you want dynamic programming, which is precisely divide and conquer plus memoisation.

• The base case must be reachable. A "divide" that can produce an empty or full-size subproblem recurses forever. Quicksort's mid + 1 and mid - 1 exist for exactly this reason.
• Recursion depth is $O(\log n)$ when balanced and $O(n)$ when not. Unbalanced quicksort overflows the stack rather than merely running slowly.
• Switch to an iterative algorithm at small sizes. Recursion overhead dominates below ~16 elements, which is why production sorts fall back to insertion sort.
• The Master Theorem does not cover everything — it requires subproblems of equal size and well-behaved f(n). Unequal splits need the Akra–Bazzi method or a recursion tree.

Recall

InvariantDivide and conquer only pays off when the subproblems are independent — no shared state between them — which is exactly what lets divide, conquer, and combine be reasoned about (and often parallelised) separately.

Costs

mergesort: 2T(n/2) + $O(n)$ (worst)$O(n\log n)$

binary search: T(n/2) + $O(1)$ (worst)$O(\log n)$

balanced binary tree traversal: 2T(n/2) + $O(1)$ (worst)$O(n)$

Karatsuba multiplication: 3T(n/2) + $O(n)$ (worst)$O(n^{1.58})$

Strassen's matrix multiply: 7T(n/2) + $O(n^2)$ (worst)$O(n^{2.81})$

Reach for itThe problem splits cleanly into independent subproblems of the same kind, small enough that a base case is reachable.

TrapApplying divide and conquer to subproblems that overlap. Naive Fibonacci recomputes the same calls exponentially often — that is dynamic programming's problem to solve, not this pattern's.

References

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, Ch. 4 — divide and conquer, the substitution and recursion-tree methods, and the Master Theorem with proof.
• Karatsuba, A. (1962) — the multiplication algorithm that first beat the schoolbook $O(n^2)$ bound.
• Strassen, V. (1969), "Gaussian elimination is not optimal" — the matrix-multiplication result.

Books & Videos

• Bentley, J., Programming Pearls, Ch. 8 — the maximum-subarray problem worked through four algorithms, including the divide-and-conquer one above.

Related Pages

• Mergesort and Quicksort — the two canonical instances.
• Dynamic Programming — what to use when subproblems overlap.
• Recurrences & the Master Theorem — the general method for solving the recurrence a divide-and-conquer algorithm produces.