Divide and Conquer

In Turkish: Böl ve Yönet
Pronunciation: dih-VYDE and KONG-ker

Updated September 30, 20263 min read

In short

Divide and conquer is an algorithm design technique that splits a problem into smaller independent parts, solves each recursively, and combines the results.

What is divide and conquer?

Divide and conquer is a strategy for designing algorithms in three steps. First, divide the problem into smaller subproblems of the same kind; second, conquer each subproblem by solving it recursively, until the pieces are small enough to solve directly; third, combine the partial answers into the answer for the whole problem. The small, directly solvable case is called the base case.

The running time of a divide and conquer algorithm depends on how many subproblems it creates, how big they are, and how much work dividing and combining take. Merge sort splits a list into two halves, sorts each, and merges them in linear time, which adds up to O(n log n), while binary search is a simpler case that divides the range but only needs to continue in one half. Such costs are written as recurrences, like T(n) = 2T(n/2) + O(n) for merge sort, and a standard result called the master theorem solves many of them. Because the subproblems are independent, they can often be solved in parallel on different CPU cores or machines.

It is how a teacher might grade a thousand exams: split the pile among ten assistants, let each split theirs further if needed, then gather the finished piles. Classic divide and conquer algorithms include merge sort, quicksort, binary search, Karatsuba's fast multiplication of large numbers, the fast Fourier transform (FFT) used in audio and signal processing, and finding the closest pair of points. The same idea appears at a larger scale in distributed data processing, where a huge job is split across many machines and the partial results are combined.

Divide and conquer is often confused with dynamic programming, which also breaks problems into subproblems. The difference is overlap: in divide and conquer the subproblems are independent, so each is solved once anyway, while in dynamic programming the same subproblems recur many times, so their results are stored and reused. It is also related to, but broader than, recursion: recursion is a coding technique, while divide and conquer is a way of structuring a solution that is usually written recursively.

Key takeaways

Divide and conquer splits a problem into independent subproblems, solves each recursively, and combines the answers.
Merge sort, quicksort, binary search, and the fast Fourier transform are classic examples.
Running times are described by recurrences such as T(n) = 2T(n/2) + O(n), which gives O(n log n).
Independent subproblems make many divide and conquer algorithms easy to parallelize.
Dynamic programming is used instead when subproblems overlap and repeat.

Example

Fast exponentiation by halving the problempython

def power(base, exp):
    # Divide: x^n = (x^(n/2))^2, so each step halves the exponent
    if exp == 0:
        return 1                      # base case: solved directly
    half = power(base, exp // 2)      # conquer the smaller subproblem once
    result = half * half              # combine
    return result * base if exp % 2 else result

print(power(3, 13))                 # 1594323
print(power(2, 1000) == 2 ** 1000)  # True, after only about 10 levels of recursion

Readers ask

What is the difference between divide and conquer and dynamic programming?

Both split a problem into subproblems, but divide and conquer works when the subproblems are independent, so each one is solved once. Dynamic programming is for subproblems that overlap, and it stores their answers so they aren't recomputed.

Is binary search divide and conquer?

Yes, in a simple form: it divides the search range in half and continues in only one half, with no combine step. Some textbooks call this special case decrease and conquer.

Which sorting algorithms use divide and conquer?

Merge sort and quicksort are the classic ones. Merge sort does its real work when combining, by merging sorted halves, while quicksort does it when dividing, by partitioning the items around a pivot.