What is Divide and Conquer

Divide and conquer is an algorithm design strategy with three steps: divide the problem into smaller subproblems, conquer each subproblem recursively, and combine the results into a solution for the original problem. The key insight is that the subproblems are independent — solving one does not depend on the answer to another.

How it works

Merge sort is the textbook example:

1. Divide — split the array in half.
2. Conquer — recursively sort each half.
3. Combine — merge the two sorted halves into one sorted array.

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

Each level divides the problem in half, and each level's merge does O(n) work. There are O(log n) levels, giving O(n log n) total.

Quicksort follows the same pattern but does its work during the divide step (partitioning around a pivot) rather than during the combine step.

Binary search is divide and conquer reduced to its simplest form: divide in half, conquer only the relevant half, no combine step needed.

Divide and conquer differs from dynamic programming in a critical way: divide-and-conquer subproblems are independent (sorting the left half doesn't depend on the right half), while DP subproblems overlap (computing fib(5) and fib(4) both need fib(3)). When subproblems overlap, DP with memoization is the right approach. When they are independent, divide and conquer is cleaner and often parallelizable.

Why it matters

Divide and conquer is the strategy behind the fastest comparison sorts (merge sort, quicksort), fast multiplication (Karatsuba), and many geometric algorithms (closest pair of points). Its recursive structure makes it natural to parallelize — each subproblem can run on a separate core. Understanding the pattern lets you recognize when a problem can be split and conquered rather than solved all at once.

See How Sorting Works and How Recursion Works for detailed walkthroughs.