Merge Sort

Explanation

Merge sort has three steps: divide (split the array into two halves), conquer (recursively sort each half), merge (combine the two sorted halves into one sorted array). The merge step is the key operation: given two sorted arrays, create a single sorted array by repeatedly comparing the front elements of each and taking the smaller one. This merge takes O(n) time, and the recursion has O(log n) levels, giving O(n log n) total. Unlike quick sort, merge sort's worst case is also O(n log n) — it doesn't depend on pivot selection or input order. This predictability makes merge sort preferable when worst-case guarantees matter. Merge sort is also stable: equal elements maintain their original relative order. Stability matters when sorting by multiple keys: sort by last name, then by first name, and equal last names stay in their original first-name order. The downside is O(n) extra space: the merge step needs an auxiliary array to store merged results. In-place merge sort variants exist but are significantly more complex. For sorting linked lists, merge sort is actually the optimal algorithm — linked lists' lack of random access makes quick sort impractical, and merge sort only requires pointer manipulation, not auxiliary space. Timsort, the sorting algorithm used by Python and Java, is a hybrid of merge sort and insertion sort. It identifies already-sorted "runs" in the data and merges them, achieving O(n) for nearly-sorted data and O(n log n) in general. This is why Python's sort is extremely fast in practice.

Code Example

// Merge sort — recursive, O(n log n), stable
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++]); // <= for stability
    else                     result.push(right[j++]);
  }

  // Append remaining elements
  while (i < left.length)  result.push(left[i++]);
  while (j < right.length) result.push(right[j++]);

  return result;
}

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

Why It Matters for Engineers

Merge sort teaches the most important algorithm design paradigm: divide and conquer. The pattern of "split the problem in half, solve recursively, combine results" generalizes to binary search, fast Fourier transforms, nearest-neighbor algorithms, and many other foundational algorithms. Understanding how merge sort achieves O(n log n) gives you the intuition to analyze any divide-and-conquer algorithm. Merge sort is also the basis for external sorting — sorting datasets too large to fit in RAM. External merge sort works by loading chunks of data into memory, sorting each chunk, writing sorted chunks to disk, and then merging the sorted chunks. This is how databases sort large tables and how MapReduce's shuffle phase works.