Divide and conquer

Overview

Divide and conquer solves a problem by splitting it into independent smaller subproblems of the same type, solving each recursively, and combining their answers. Merge sort, quicksort, binary search, fast exponentiation, and closest pair of points all follow this shape.

It differs from dynamic programming because the subproblems do not overlap: each piece is solved once. The cost is analyzed with a recurrence, such as T(n) = 2T(n/2) + O(n) for merge sort, which the Master Theorem solves to O(n log n).

When to use it

• The input splits naturally into halves or independent parts.
• The combine step is cheaper than solving the whole problem directly.
• Counting problems that can be solved during a merge (inversions, reverse pairs).
• Building balanced structures from sorted data, or tree problems with left and right halves.

Problem patterns it solves

Where it is used in real software

Key terms

Divide

Split the input into smaller independent parts.

Conquer

Solve each part recursively; tiny parts are base cases.

Combine

Merge the partial answers into the full answer.

Recurrence

T(n) = aT(n/b) + f(n), describing the total cost.

How it works, step by step

1. 1
   Define the base case

   An empty or single-element input is solved directly.

2. 2
   Split

   Usually at the middle: mid = (lo + hi) >> 1.

3. 3
   Solve both halves recursively

   Trust that each returns a correct answer for its half.

4. 4
   Combine

   Merge sorted halves, sum counts, or compute the answer that crosses the middle.

5. 5
   Analyze with the Master Theorem

   Compare the number of subproblems with the cost of combining.

Counting inversions with merge sort

arr = [2, 4, 1, 3, 5]; an inversion is i < j with arr[i] > arr[j]

Total inversions = 3: (2,1), (4,1), (4,3). When an element from the right half is placed first, it is smaller than every remaining element in the left half, so all of them form inversions at once. O(n log n) instead of O(n^2).

Implementation

1function countInversions(arr) {2  function sortCount(a) {3    if (a.length <= 1) return [a, 0];4    const mid = a.length >> 1;5    const [left, leftCount] = sortCount(a.slice(0, mid));6    const [right, rightCount] = sortCount(a.slice(mid));7    const merged = [];8    let i = 0, j = 0, cross = 0;9    while (i < left.length && j < right.length) {10      if (left[i] <= right[j]) merged.push(left[i++]);11      else {12        merged.push(right[j++]);13        cross += left.length - i; // every remaining left element is larger14      }15    }16    return [merged.concat(left.slice(i), right.slice(j)), leftCount + rightCount + cross];17  }18  return sortCount(arr)[1];19}20 21// 50. Pow(x, n): T(n) = T(n/2) + O(1) = O(log n)22function myPow(x, n) {23  if (n === 0) return 1;24  if (n < 0) return 1 / myPow(x, -n);25  const half = myPow(x, Math.floor(n / 2));26  return n % 2 === 0 ? half * half : half * half * x;27}28 29// 23. Merge k Sorted Lists by merging pairs in rounds: O(N log k)30function mergeKLists(lists) {31  if (!lists.length) return null;32  while (lists.length > 1) {33    const next = [];34    for (let i = 0; i < lists.length; i += 2) next.push(mergeTwo(lists[i], lists[i + 1] ?? null));35    lists = next;36  }37  return lists[0];38}39 40function mergeTwo(a, b) {41  const dummy = { next: null };42  let tail = dummy;43  while (a && b) {44    if (a.val <= b.val) { tail.next = a; a = a.next; } else { tail.next = b; b = b.next; }45    tail = tail.next;46  }47  tail.next = a ?? b;48  return dummy.next;49}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Unbalanced splits.

  Fix: Quicksort with bad pivots degrades to O(n^2); split at the middle or randomize.

• Copying arrays with slice at every level.

  Fix: Pass index ranges and a shared buffer to reduce memory and allocation.

• Missing the crossing case.

  Fix: When the answer can span both halves (max subarray), compute it explicitly in the combine step.

Interview questions

Practice problems