Divide and Conquer, with Merge Sort

Divide and conquer is the strategy behind some of the most important algorithms that exist, and it's really just recursion with a specific shape: split the problem, solve the pieces the same way, and combine. This lesson works through merge sort as the clearest possible example — not because you'll hand-write sorts often (the next lesson covers when the built-in sort is enough, which is almost always), but because the reasoning that proves merge sort is O(n log n) is a template you'll reuse for analyzing other divide-and-conquer code.

The strategy, in three steps

1. Divide — split the problem into smaller subproblems of the same kind.
2. Conquer — solve each subproblem, typically by applying the same strategy recursively, down to a base case trivial enough to answer directly.
3. Combine — merge the subproblems' solutions into the solution for the original, larger problem.

Merge sort, following the recipe exactly

function mergeSort(arr) {
  if (arr.length <= 1) return arr; // base case — already "sorted"
 
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));   // divide + conquer, left half
  const right = mergeSort(arr.slice(mid));      // divide + conquer, right half
 
  return merge(left, right);                    // combine
}
 
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++]);
  }
 
  // one side may have leftovers once the other is exhausted — append them
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);
 
  return result;
}

Divide: split the array in half. Conquer: sort each half by calling mergeSort again (the recursive case) until arrays are down to size 0 or 1 (the base case — a single element is trivially "sorted"). Combine: merge walks both already-sorted halves with two pointers — the same two-pointer technique from earlier in this course — picking whichever front element is smaller, until one side runs out.

Proving it's O(n log n), not O(n²)

This is the part worth internalizing, because the same two-piece argument (how deep does the recursion go, and how much work happens at each level) generalizes to analyzing other divide-and-conquer algorithms you'll meet later.

How deep is the recursion? Every level splits the array exactly in half. Going from n elements down to arrays of size 1 by repeatedly halving takes log₂(n) steps — that's the definition of a logarithm. So the recursion is log(n) levels deep.

How much work happens at each level? At any given level of the recursion, the subarrays at that level, added together, still contain all n original elements — they've just been split into more, smaller pieces. Merging is linear in the combined size of what's being merged, so the total merging work across one entire level — summed across every merge happening at that level — is O(n), regardless of how many pieces that level has been split into.

Multiply: O(n) work per level, across O(log n) levels, gives O(n log n) total. This is strictly better than the O(n²) sorts (like a naive bubble or insertion sort) for large n — at a million elements, n log n is around 20 million operations; n² is a trillion.

The space cost, and why it's a deliberate trade

merge builds a brand-new result array at every call, and slice() creates new arrays for every split. This makes merge sort O(n) auxiliary space — not in-place, unlike some O(n log n) alternatives (quicksort, covered only briefly in the next lesson, is typically in-place but doesn't have merge sort's worst-case guarantee).

That space cost buys two real properties: a guaranteed O(n log n) even in the worst case (some in-place sorts degrade to O(n²) on specific unlucky inputs), and stability — equal elements keep their original relative order, which matters whenever you're sorting objects by one field but want ties broken by "whichever came first."

What to remember

• Divide and conquer: split into smaller subproblems of the same kind, solve each one recursively, combine the results.
• Merge sort's complexity proof has two parts: the recursion is log(n) levels deep (repeated halving), and each level's total merge work is O(n) — multiplying gives O(n log n) overall. This two-part argument generalizes to other divide-and-conquer algorithms.
• Merge sort trades O(n) auxiliary space (new arrays at every merge) for a guaranteed worst-case O(n log n) and stability — a deliberate trade, not a flaw.
• The merge step itself reuses the two-pointer technique from earlier in this course — recognizing that reuse is a preview of how these patterns compose in real, larger algorithms.