Divide and Conquer

Divide and conquer splits a problem into smaller independent sub-problems, solves each recursively, then combines the results — the pattern behind merge sort and the Master theorem.

6 min read Level 3/5 #dsa#recursion#divide-and-conquer

What you'll learn

Describe the divide, conquer, and combine steps of the paradigm
Implement merge sort as a canonical divide-and-conquer algorithm
Apply the three cases of the Master theorem to read off time complexity

Divide and conquer is a recursive design strategy built on three steps:

Divide — split the input into two or more smaller sub-problems.
Conquer — solve each sub-problem recursively (base case solves it directly).
Combine — merge the sub-problem solutions into a solution for the full input.

This pattern appears in merge sort, quick sort, binary search, fast Fourier transforms, and many more fundamental algorithms.

Merge Sort

Merge sort is the clearest illustration. Divide the array in half, sort each half recursively, then merge the two sorted halves:

function mergeSort(arr) {
  // Base case: arrays of 0 or 1 element are already sorted
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);

  // Divide
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  // Combine
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  // Append any remaining elements
  return result.concat(left.slice(i)).concat(right.slice(j));
}

console.log(mergeSort([5, 3, 8, 1, 9, 2])); // [1, 2, 3, 5, 8, 9]

The recursion tree has depth log n (each level halves the input). At each level, the total work done across all merge calls is O(n). Combined: O(n log n).

The Master Theorem (Three Cases)

The Master theorem gives a shortcut for recurrences of the form T(n) = a·T(n/b) + f(n) — where a sub-problems of size n/b are solved and f(n) is the cost of the divide and combine steps:

Case	Condition	Result	Example
1	f(n) = O(n^(log_b a - ε))	T(n) = Θ(n^log_b a)	Binary search tree building
2	f(n) = Θ(n^(log_b a) · log^k n)	T(n) = Θ(n^log_b a · log^(k+1) n)	Merge sort: k=0 → O(n log n)
3	f(n) = Ω(n^(log_b a + ε))	T(n) = Θ(f(n))	Matrix-vector multiply

For merge sort: a = 2, b = 2, so log_b a = 1. The combine step is f(n) = O(n), which matches Case 2 with k=0, giving T(n) = O(n log n).

Choosing Sub-Problem Boundaries

The key design decision is how to divide:

Equal halves (merge sort, binary search) guarantees balanced recursion and a predictable depth of log n.
Pivot-based split (quick sort) is fast on average but O(n²) in the worst case if pivots are always extremes.
Overlap allowed (dynamic programming) — when sub-problems share computation, memoization or tabulation avoids repeated work.

Up Next

Backtracking is a specialization of recursion where you explore all possible choices and undo them if they lead to a dead end — starting with generating every permutation of a set.

Permutations via Backtracking →