Divide and Conquer: Break, Solve, Combine

Divide and conquer is an algorithm design strategy that solves a problem in three steps: divide it into smaller subproblems of the same type, conquer each subproblem by solving it recursively, then combine their answers into the solution for the whole. It’s recursion with a structure — and it powers some of the fastest algorithms there are, including merge sort, quick sort, and binary search.

The three steps

Divide — split the input into smaller pieces (often two halves).
Conquer — solve each piece recursively. The base case is a piece small enough to answer directly (size 0 or 1).
Combine — merge the sub-answers into the final answer. This step is where the real work — and the cleverness — usually lives.

For beginners: Backtracking explores choices; divide and conquer splits data. Both are recursive, but divide and conquer always partitions the input and stitches results back together, while backtracking builds and abandons candidate solutions.

Example: merge sort

Merge sort divides an array in half, sorts each half recursively, then merges the two sorted halves into one sorted array. The merge step is the heart of it.

std::vector<int> mergeSort(std::vector<int> a) {
    if (a.size() <= 1) return a;                  // base case
    int mid = a.size() / 2;
    std::vector<int> left(a.begin(), a.begin() + mid);   // DIVIDE
    std::vector<int> right(a.begin() + mid, a.end());
    left = mergeSort(left);                        // CONQUER
    right = mergeSort(right);
    std::vector<int> merged;                       // COMBINE
    int i = 0, j = 0;
    while (i < (int)left.size() && j < (int)right.size())
        merged.push_back(left[i] <= right[j] ? left[i++] : right[j++]);
    while (i < (int)left.size())  merged.push_back(left[i++]);
    while (j < (int)right.size()) merged.push_back(right[j++]);
    return merged;
}

int[] mergeSort(int[] a) {
    if (a.length <= 1) return a;                   // base case
    int mid = a.length / 2;
    int[] left  = mergeSort(Arrays.copyOfRange(a, 0, mid));   // DIVIDE + CONQUER
    int[] right = mergeSort(Arrays.copyOfRange(a, mid, a.length));
    int[] merged = new int[a.length];              // COMBINE
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length)
        merged[k++] = (left[i] <= right[j]) ? left[i++] : right[j++];
    while (i < left.length)  merged[k++] = left[i++];
    while (j < right.length) merged[k++] = right[j++];
    return merged;
}

function mergeSort(a) {
  if (a.length <= 1) return a;                     // base case
  const mid = Math.floor(a.length / 2);
  const left  = mergeSort(a.slice(0, mid));        // DIVIDE + CONQUER
  const right = mergeSort(a.slice(mid));
  const merged = [];                               // COMBINE
  let i = 0, j = 0;
  while (i < left.length && j < right.length)
    merged.push(left[i] <= right[j] ? left[i++] : right[j++]);
  while (i < left.length)  merged.push(left[i++]);
  while (j < right.length) merged.push(right[j++]);
  return merged;
}

def merge_sort(a):
    if len(a) <= 1:
        return a                                   # base case
    mid = len(a) // 2
    left = merge_sort(a[:mid])                      # DIVIDE + CONQUER
    right = merge_sort(a[mid:])
    merged = []                                     # COMBINE
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

It splits log n times, and each level does O(n) merging → O(n log n) time. Full treatment on the merge sort page.

The cost: recurrences

Divide-and-conquer running time is captured by a recurrence — a formula that defines the cost in terms of smaller inputs. Merge sort’s is:

T(n) = 2 T(n/2) + O(n)      ->  O(n log n)

Read it as “two halves, plus O(n) to combine.” Binary search’s is T(n) = T(n/2) + O(1) → O(log n), because it throws away half the input and does constant combine work. The general tool for solving these is the Master Theorem, covered in analyzing recursive code.

A leaner example: binary search

Binary search is divide and conquer with a trivial combine step — it discards one half and recurses into the other, so there’s nothing to merge back.

int binarySearch(const std::vector<int>& a, int target, int lo, int hi) {
    if (lo > hi) return -1;                  // base case: not found
    int mid = lo + (hi - lo) / 2;            // avoid overflow
    if (a[mid] == target) return mid;
    if (a[mid] < target) return binarySearch(a, target, mid + 1, hi);
    return binarySearch(a, target, lo, mid - 1);
}

int binarySearch(int[] a, int target, int lo, int hi) {
    if (lo > hi) return -1;                  // base case: not found
    int mid = lo + (hi - lo) / 2;            // avoid overflow
    if (a[mid] == target) return mid;
    if (a[mid] < target) return binarySearch(a, target, mid + 1, hi);
    return binarySearch(a, target, lo, mid - 1);
}

function binarySearch(a, target, lo, hi) {
  if (lo > hi) return -1;                    // base case: not found
  const mid = lo + Math.floor((hi - lo) / 2);
  if (a[mid] === target) return mid;
  if (a[mid] < target) return binarySearch(a, target, mid + 1, hi);
  return binarySearch(a, target, lo, mid - 1);
}

def binary_search(a, target, lo, hi):
    if lo > hi:
        return -1                # base case: not found
    mid = lo + (hi - lo) // 2
    if a[mid] == target:
        return mid
    if a[mid] < target:
        return binary_search(a, target, mid + 1, hi)
    return binary_search(a, target, lo, mid - 1)

Going deeper: Computing mid = lo + (hi - lo) / 2 instead of (lo + hi) / 2 avoids integer overflow when lo + hi exceeds the int range — a famous bug that lurked in production binary searches for years. Full coverage on the binary search page.

Where you’ll meet divide and conquer

Merge sort and quick sort — sorting in O(n log n).
Binary search — O(log n) lookup in sorted data.
Many tree algorithms — a tree is a divide-and-conquer structure.

Tip: When a problem says “the answer for the whole can be built from the answers for halves,” reach for divide and conquer. When subproblems overlap and repeat, switch to dynamic programming instead so you don’t recompute them.

Next: lock it in with the recursion & backtracking exercises.