Merge Sort

Merge sort solves the sorting problem by breaking it into smaller versions of itself: it splits the array in half, recursively sorts each half, then combines the two sorted halves into one sorted array. The recursion bottoms out at arrays of length 1, which are trivially “sorted” already.

This divide-and-conquer shape — split the problem, solve the pieces, combine the results — is the same pattern behind binary search, though binary search only recurses into one half while merge sort recurses into both.

The actual sorting work happens in the merge step, not the split. Given two already-sorted arrays, merging them into one sorted array takes a single linear pass: compare the front of each array, take the smaller one, and repeat until both arrays are exhausted.

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++]);
  }

  // append whatever remains — only one of these has leftover elements
  while (i < left.length) result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);

  return result;
}

Merging two arrays of total size n takes O(n) — every element is looked at exactly once.

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

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

  return merge(left, right);
}

Think of the recursion as a tree. At the top level, one call handles all n elements. At the next level, two calls each handle n/2 elements — n elements of work total. One level down, four calls each handle n/4 elements — still n elements of work total. Every level of the tree does O(n) work in its merge steps, regardless of how many calls that level contains.

The array halves at each level, so the tree has log₂(n) levels — the same halving logic covered in the time complexity guide. Multiply: O(n) work per level × O(log n) levels = O(n log n) total.

Unlike quicksort, merge sort’s time complexity doesn’t depend on the input order — it always splits the array exactly in half and always does a full O(n) merge at each level, regardless of whether the input is already sorted, reverse-sorted, or random.

That consistency is merge sort’s main selling point over quicksort, which is O(n log n) on average but degrades to O(n²) on adversarial input.

Merge sort is notin-place: the merge step builds new arrays to hold the merged results rather than rearranging the input in place. That costs O(n) auxiliary space — at any given time, the temporary arrays across the recursion hold at most n elements total. This is the main tradeoff against in-place O(n log n) sorts like heapsort, which sorts in O(1) extra space but isn’t stable.

Sorting [38, 27, 43, 3, 9, 82, 10]:

• Split: [38, 27, 43] and [3, 9, 82, 10]
• Split again: [38], [27, 43], [3, 9], [82, 10]
• Split to base case:[38], [27], [43], [3], [9], [82], [10] — all length 1, already “sorted”
• Merge up: [27, 43], [3, 9], [10, 82] (and [38] stays as-is)
• Merge up: [27, 38, 43], [3, 9, 10, 82]
• Final merge: [3, 9, 10, 27, 38, 43, 82]

• Big-O Cheat Sheet — see where O(n log n) ranks among the other complexity classes.
• How to Analyze Time Complexity of Any Algorithm — the general method, including how sequential and nested work combine.
• Binary Search — an O(log n) algorithm that depends on data merge sort can prepare.
• Quicksort — the in-place O(n log n)-average alternative, with a worst-case tradeoff merge sort avoids.
• Space Complexity Explained — why merge sort’s O(n) auxiliary space is the tradeoff for its guaranteed time complexity.