Merge Sort

Merge sort divides the array in half, recursively sorts each half, and then merges the sorted halves back together.

How It Works

1. Divide the array into two halves.
2. Recursively sort each half.
3. Merge the two sorted halves into one sorted array.

Example

function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(a: number[], b: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;

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

  return [...result, ...a.slice(i), ...b.slice(j)];
}

console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]

Complexity

Why Always O(n log n)?

Unlike quicksort, merge sort always divides exactly in half, so the recursion depth is always log n, and each level does O(n) work for merging.

Key Properties

• Stable — equal elements keep their original order.
• Not in-place — requires O(n) extra memory for the merge step.
• Predictable — no worst-case degradation like quicksort.