Merge sort

Split in half, sort each half, merge. Always O(n log n) and stable.

How it works

Recursively split down to one element, which is already sorted. Merging two sorted lists is a linear walk with two pointers. log n levels of splitting, n work per level. Stable means equal items keep their original order, which matters when sorting records by one field after another.

Reach for it when

• Need guaranteed n log n
• Need a stable sort
• Linked lists (no random access needed)
• Data too big for memory (external sort)

Copyfunction mergeSort(a) {
  if (a.length <= 1) return a;
  const mid = a.length >> 1;
  const l = mergeSort(a.slice(0, mid)),
    r = mergeSort(a.slice(mid));
  const out = [];
  let i = 0,
    j = 0;
  while (i < l.length && j < r.length) out.push(l[i] <= r[j] ? l[i++] : r[j++]); // <= keeps it stable
  return out.concat(l.slice(i), r.slice(j));
}

Traps

• Use <= in the merge to keep it stable.
• slice() in every call costs memory. Fine for interviews; mention it.