Merge sort and divide and conquer

Merge sort splits the array in half, sorts each half recursively, and merges the two sorted halves. The merge is the whole trick: combining two sorted lists takes one linear pass.

function mergeSort(a) {
  if (a.length <= 1) return a;

  const mid = a.length >> 1;
  return merge(mergeSort(a.slice(0, mid)), mergeSort(a.slice(mid)));
}

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

  while (i < left.length && j < right.length) {
    // <= keeps equal elements in their original order: this is what makes it stable.
    if (left[i] <= right[j]) out.push(left[i++]);
    else out.push(right[j++]);
  }

  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);

  return out;
}

Why O(n log n)

Halving reaches length 1 after log₂ n levels, and every level merges a total of n elements. n work × log n levels = O(n log n) — in the best, average and worst case. Merge sort never degrades.

The price is O(n) extra space for the merge buffer, and that is its main disadvantage against quicksort.

What it is good at

• Stability. Equal elements keep their relative order, which matters when sorting by one key after another.
• Predictability. No pathological input, which suits real-time and adversarial contexts.
• Linked lists. Merging needs no random access, so linked lists sort in O(n log n) with O(1) extra space — merge sort is the standard answer for "sort a linked list".
• Data too large for memory. External merge sort streams sorted runs from disk, which is how databases sort tables larger than RAM.

The pattern beneath it

Divide and conquer recurs throughout this course: split the problem, solve the parts, combine. The Master Theorem gives the cost — T(n) = 2T(n/2) + O(n) resolves to O(n log n).

The same skeleton with a different combine step counts inversions (how far a list is from sorted) in O(n log n) instead of O(n²) — a favourite follow-up question, and worth implementing once.