Merge Sort

Merge Sort

Merge sort is a divide-and-conquer algorithm, and it's one of the most reliable sorting algorithms out there. The strategy is elegant: split the array in half, sort each half recursively, then merge the two sorted halves back together. It's like organizing a deck of cards by splitting it into smaller piles, sorting each pile, then combining them.

The beauty of merge sort is its guaranteed O(n log n) performance. Unlike quick sort, there's no bad worst case. The trade-off? It needs O(n) extra space for the merging step. But for most applications, that's a worthwhile exchange for predictable performance.

Split Phase and Merge Phase

The split phase keeps dividing the array until you have single elements — which are trivially sorted. Think of it like cutting a loaf of bread into individual slices. For [38, 27, 43, 3, 9, 82, 10], you'd split into [38, 27, 43, 3] and [9, 82, 10], then keep going until you reach single elements.

The merge phase is where the magic happens. You take two sorted subarrays and combine them by always picking the smaller front element. It's like merging two sorted stacks of papers — you just compare the top of each stack and take the smaller one. This merge step runs in O(n) time.

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);
}
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++]);
    }
  }
  return result.concat(left.slice(i), right.slice(j));
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));

Time Complexity

Merge sort always runs in O(n log n) time, regardless of the input. The array is split log(n) times, and each merge pass takes O(n) time. That consistency is merge sort's biggest advantage — no surprises, no worst-case degradation.

The space complexity is O(n) because you need temporary arrays during the merge step. This is the main drawback compared to in-place algorithms like quick sort. For very large datasets where memory is tight, this matters.

When to Choose Merge Sort

Merge sort is the algorithm of choice when you need guaranteed O(n log n) performance. It's also stable, making it great for sorting complex objects by multiple criteria. Many standard library implementations use merge sort or a hybrid variant.

It's particularly good for linked lists — you don't need extra space for merging since you can relink nodes. It's also excellent for external sorting when data doesn't fit in memory, since it accesses elements sequentially.