Algorithms
  • Understand the three steps: divide, conquer, combine
  • See how divide and conquer achieves O(n log n) from O(n²)
  • Learn when to use divide and conquer vs greedy or dynamic programming

Introduction to Divide and Conquer

You need to find a name in a phone book with a million entries. Flipping through page by page would take forever.

Instead, you open the middle. If your name comes before the middle, search the left half. Otherwise, search the right half. Repeat until you find it.

You just cut the problem in half, over and over. That's divide and conquer.

The Strategy

Divide and conquer breaks problems into smaller pieces, solves them independently, then combines the results.

Three steps:

  1. Divide: Split the problem into smaller subproblems
  2. Conquer: Solve each subproblem (usually recursively)
  3. Combine: Merge the solutions

For the phone book:

  • Divide: Split at the middle
  • Conquer: Search the relevant half
  • Combine: Return the result (no combining needed here—once you find it, you're done)

Merge Sort: A Classic Example

Sorting [38, 27, 43, 3, 9, 82, 10] with merge sort.

Divide: Split the array in half repeatedly until you have arrays of size 1.

[38, 27, 43, 3, 9, 82, 10]
           ↓
    [38, 27, 43, 3]    [9, 82, 10]
           ↓                ↓
  [38, 27]  [43, 3]     [9, 82]  [10]
     ↓         ↓           ↓       ↓
  [38] [27] [43] [3]    [9] [82]  [10]

Conquer: Arrays of size 1 are already sorted.

Combine: Merge pairs of sorted arrays.

Merge [38] and [27] → [27, 38]
Merge [43] and [3] → [3, 43]
Merge [9] and [82] → [9, 82]
[10] stays as is

Merge [27, 38] and [3, 43]:
  Compare 27 and 3 → take 3
  Compare 27 and 43 → take 27
  Compare 38 and 43 → take 38
  Take 43
  Result: [3, 27, 38, 43]

Merge [9, 82] and [10]:
  Compare 9 and 10 → take 9
  Compare 82 and 10 → take 10
  Take 82
  Result: [9, 10, 82]

Merge [3, 27, 38, 43] and [9, 10, 82]:
  Compare 3 and 9 → take 3
  Compare 27 and 9 → take 9
  Compare 27 and 10 → take 10
  Compare 27 and 82 → take 27
  Compare 38 and 82 → take 38
  Compare 43 and 82 → take 43
  Take 82
  Result: [3, 9, 10, 27, 38, 43, 82]

Done. The array is sorted.

Why This Works

Smaller problems are easier: Sorting two elements is trivial. Merging two sorted lists is straightforward.

Logarithmic depth: Each level halves the problem size. For n elements, you have log₂(n) levels. For 1 million elements, that's only 20 levels.

Combining is efficient: Merging two sorted arrays of size n/2 takes O(n) time—just walk through both lists.

Total time: O(n) per level × O(log n) levels = O(n log n).

Compare to bubble sort's O(n²). For n=1,000,000, that's 1 trillion operations vs 20 million. Divide and conquer wins.

Binary Search

Find 43 in [3, 9, 10, 27, 38, 43, 82] (sorted array).

Check middle: array[3] = 27
43 > 27, search right half: [38, 43, 82]

Check middle: array[1] = 43
Found it at index 5 (overall)

Each step cuts the problem in half. For n elements, you need at most log₂(n) comparisons.

Linear search would check every element—up to n comparisons. Binary search checks log₂(n).

For n=1,000,000: linear search = 1 million comparisons, binary search = 20 comparisons.

The General Pattern

Most divide and conquer algorithms follow this structure:

def divide_conquer(problem):
    # Base case: problem small enough to solve directly
    if len(problem) <= 1:
        return solve_directly(problem)
    
    # Divide: split into subproblems
    mid = len(problem) // 2
    left_subproblem = problem[:mid]
    right_subproblem = problem[mid:]
    
    # Conquer: solve subproblems recursively
    left_solution = divide_conquer(left_subproblem)
    right_solution = divide_conquer(right_subproblem)
    
    # Combine: merge solutions
    return combine(left_solution, right_solution)

The trick is figuring out how to divide and how to combine.

When to Use Divide and Conquer

The problem can be split: You can break it into independent subproblems of the same type.

Subproblems are similar: Each piece looks like a smaller version of the original.

Combining is efficient: Merging solutions doesn't negate the gains from dividing.

Examples that fit:

  • Sorting (merge sort, quicksort)
  • Searching (binary search)
  • Matrix multiplication (Strassen's algorithm)
  • Closest pair of points
  • Fast Fourier Transform

Examples that don't:

  • Problems where subproblems overlap heavily (use dynamic programming instead)
  • Problems where you can't split cleanly

The Recurrence Relation

Divide and conquer algorithms have a mathematical pattern. For merge sort:

T(n) = 2T(n/2) + O(n)

Translation:

  • T(n): time to sort n elements
  • 2T(n/2): time to sort two halves (divide/conquer)
  • O(n): time to merge (combine)

By the Master Theorem (a mathematical tool for solving recurrences), this resolves to O(n log n).

For binary search:

T(n) = T(n/2) + O(1)

Only one subproblem, constant combine time. This gives O(log n).

Understanding recurrences helps you analyze divide and conquer algorithms without implementing them.

Divide and Conquer vs Other Paradigms

vs Greedy: Greedy makes one choice and commits. Divide and conquer explores both halves (or all subproblems) and combines results.

vs Dynamic Programming: Both break problems into subproblems. But DP has overlapping subproblems—you solve the same subproblem multiple times, so you cache results. Divide and conquer has independent subproblems.

vs Brute Force: Brute force tries everything. Divide and conquer is smarter—it exploits structure to eliminate work.

The Intuition

Think of merge sort vs bubble sort.

Bubble sort: compare adjacent elements, swap if needed, repeat. You're working globally, checking everything repeatedly. O(n²).

Merge sort: split the problem. Sort small pieces (easy). Merge sorted pieces (efficient). You're working locally at each level, never redoing work. O(n log n).

Divide and conquer is about exploiting structure. If you can split a problem such that solving the pieces and combining them is cheaper than solving the whole directly, you win.

Common Pitfalls

Over-dividing: Splitting into too many pieces can add overhead. Usually, divide into 2 or 3 subproblems.

Expensive combining: If merging takes O(n²), you lose the advantage. Keep combine step efficient (usually O(n) or O(n log n)).

Not checking base cases: Infinite recursion if you forget when to stop dividing.

Assuming all problems fit: Not everything benefits from divide and conquer. If subproblems overlap, use DP. If one greedy choice suffices, use greedy.

The Power

Divide and conquer turns many O(n²) problems into O(n log n). For large n, that's the difference between feasible and impossible.

Sorting a billion records: O(n²) = trillion-trillion operations (years). O(n log n) = 30 billion operations (seconds).

That's why merge sort, quicksort, and binary search are fundamental. They make the impossible practical.

And once you understand the pattern—divide, conquer, combine—you'll recognize where it applies and write efficient solutions instinctively.