Divide and Conquer

The general idea

Divide and conquer (in Romanian, Divide et Impera, Latin for "divide and rule") has three parts:

1. Divide the problem into smaller problems of the same kind.
2. Conquer: solve each small problem. If it is tiny (the base case), solve it directly. Otherwise do the same trick again (recursion).
3. Combine the small answers into the answer to the big problem.

It works when the small problems are independent and when combining them is cheap. See Recursion for how a function can call itself.

Merge sort: the classic example

Sort a list of n numbers:

mergeSort(list):
  if list has 1 item: return list
  left  = mergeSort(first half)
  right = mergeSort(second half)
  return merge(left, right)

Merge two sorted lists: look at the first item of each list, take the smaller one, and repeat until both are empty. Merging n items takes about n steps.

There are about log₂ n levels of splitting (8 items: 3 levels) and each level does about n work, so the total is about n log₂ n steps. This is much faster than the simple method (bubble sort), which needs about n² steps.

Binary search: halving

To find a number in a sorted list, compare it with the middle item. If it is smaller, look only at the left half; if bigger, only the right half. Each check throws away half of the items.

For n items you need at most about log₂ n checks: 16 items need 4, 1000 items need 10, and 1 000 000 items need only 20.

Other applications

• Quicksort: pick a pivot, put smaller items on its left and bigger on its right, then sort both sides.
• Fast power: a⁸ = ((a²)²)². Only 3 multiplications instead of 7. In general aⁿ = (aⁿ/²)² for even n.
• Maximum of a list: find the max of each half and take the bigger one.
• Towers of Hanoi, fast multiplication of big numbers, closest pair of points also use it.

When not to use it

If the small problems overlap (the same sub-problem appears again and again, like in Fibonacci), plain divide and conquer repeats work. Use dynamic programming instead. If you must try many choices and undo them, use backtracking.

Try it

Take 8 playing cards. Deal them into two piles of 4, then 2 and 2, then single cards. Merge pairs back, always taking the smaller top card. Count how many levels you made. In the 3D, move the state slider and predict the next state before you move it.

Key formulas and definitions

• Levels of halving for n items = log₂ n (8 → 3, 16 → 4, 1024 → 10)
• Merge sort time ≈ n × log₂ n
• Binary search checks ≤ ⌊log₂ n⌋ + 1
• Fast power: aⁿ = (aⁿ/²)² (n even), aⁿ = a × (a⁽ⁿ⁻¹⁾/²)² (n odd)

Worked examples

Common mistakes

• Forgetting the base case, so the splitting never stops.
• Using binary search on an unsorted list. The list must be sorted.
• Thinking merge sort sorts while splitting. The sorting happens while merging.
• Using divide and conquer when sub-problems overlap, which repeats work.