Divide and Conquer

Divide and conquer solves a problem by splitting it into smaller parts, solving those parts, and combining their results.

It is a design strategy, not one specific algorithm.

Core Idea

The strategy has three steps: divide the input, conquer the smaller problems, and combine the answers. It works best when the subproblems are similar to the original problem and can be solved independently.

Merge sort is a classic example because each half can be sorted separately before the merge step combines them.

Function Contract

sum_values(values) expects a list of numbers.

It returns the sum of all values by splitting the list into halves, recursively summing each half, and adding the two results. This is a teaching example for the divide-and-conquer shape, not the best way to sum a Python list in practice.

Python Example

def sum_values(values):
    if not values:
        return 0
    if len(values) == 1:
        return values[0]
 
    mid = len(values) // 2
    return sum_values(values[:mid]) + sum_values(values[mid:])

This example divides the list into halves and combines the two sums.

The Three Questions

A divide-and-conquer solution should answer three questions:

1. How is the problem divided?
2. What is the smallest problem that can be solved directly?
3. How are smaller answers combined?

For merge sort, the list is divided in half, single-element lists are base cases, and sorted halves are combined by merging.

Why It Works

Divide and conquer works when solving the smaller parts is enough to solve the whole. The combine step is the proof point. If the combine step does not preserve the meaning of the answer, the split was not useful.

For a sum, combining is addition. For sorting, combining is merging. For closest-pair geometry, combining includes checking points near the split. Different problems need different combine logic.

Complexity Shape

Many divide-and-conquer algorithms have a recurrence such as:

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

This means two half-size recursive calls plus linear combine work. Merge sort has this shape and runs in O(n log n).

Common Confusions

Divide and conquer is not the same as dynamic programming. Divide and conquer usually solves independent subproblems. Dynamic programming is useful when subproblems overlap and answers should be reused.

Recursive code is not automatically divide and conquer. The problem must actually be split into smaller pieces whose results are combined.

Another common mistake is dividing the input but doing almost all the original work again in the combine step. Then the split may not improve the algorithm.

When To Use It

Use divide and conquer when the input can be split cleanly, each part can be solved with the same idea, and the combined result is easier than solving the original directly.

Do not force it when subproblems heavily overlap. That is often a signal for dynamic programming instead.

The Main Point

Divide and conquer works when independent smaller answers can be combined into the whole answer.