Merge Sort

Merge sort is the canonical divide-and-conquer sorting algorithm. It solves the sorting problem by first solving two smaller sorting problems (the left and right halves), then combining the results. The combining step — the merge — is the heart of the algorithm.

The Divide-and-Conquer Strategy

Three steps happen at each level of recursion:

1. Divide — split the array at the midpoint into left and right halves.
2. Conquer — recursively sort each half. The base case is an array of length 0 or 1, which is already sorted.
3. Merge — walk both sorted halves in parallel, picking the smaller front element each time, until all elements have been placed into a combined sorted array.

The recurrence T(n) = 2T(n/2) + O(n) solves to T(n) = O(n log n) by the Master Theorem. Crucially this holds for best, average, and worst case — merge sort has no degenerate inputs.

JavaScript Implementation

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

  // Compare front elements and take the smaller one
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  // Append any remaining elements (at most one side has leftovers)
  return result.concat(left.slice(i)).concat(right.slice(j));
}

function mergeSort(arr) {
  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);
}

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

Why It Is Stable

The merge step picks left[i] when left[i] <= right[j]. Equal elements from the left half are always consumed before equal elements from the right half, preserving their original relative order. Merge sort is stable by design.

The O(n) Space Cost

Each merge creates a temporary array to hold the merged output. At any point in the recursion, the total auxiliary memory in use across all active stack frames is O(n). This is the main drawback compared to in-place sorts like quicksort and heap sort. In memory-constrained environments, or when sorting very large files on disk (external sorting), the space cost becomes a real concern.

Complexity

When to Use It

Merge sort is the right choice when stability is required and O(n) extra space is acceptable. It is the standard algorithm for external sorting (when data does not fit in RAM) because merging two sorted streams is efficient with sequential I/O. In practice, TimSort (V8’s built-in) is a merge sort variant that adds optimisations for real-world data.

Up Next

Quicksort achieves the same O(n log n) average case but sorts in-place — at the cost of an O(n²) worst case that a randomised pivot largely eliminates.