← Index

Searching & Sorting

Merge Sort

Split, sort, merge — guaranteed O(n log n), and stable.

What it is

Merge sort recursively splits the array in half until pieces are size 1, then merges sorted pieces back together, always taking the smaller front element from each side. Unlike quick sort, its worst case is still O(n log n) — no bad-pivot scenario can degrade it. It's also stable: equal elements keep their original relative order, which matters when sorting objects by one field.

Real-world examples

• Merging two sorted stacks of graded exams into one sorted stack — you only ever compare the top paper of each stack.
• Two people alphabetizing half a bookshelf each, then interleaving their two sorted halves back together.

Where you've probably used this already

• Array.prototype.sort() in most modern JS engines uses TimSort, a merge-sort variant, specifically because it's stable.
• External sorting — sorting a dataset too large to fit in memory (huge log files) by sorting chunks separately, then merging.
• Merging multiple already-sorted paginated API results into one combined feed.

Complexity

Code

// Merge Sort — divide and conquer sorting, O(n log n) guaranteed
// (unlike Quick Sort, which can degrade to O(n^2) on bad input).
// Split the array in half recursively until pieces are size 1,
// then merge sorted pieces back together.

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;
  let j = 0;

  // Both arrays are already sorted — walk them together, always
  // taking whichever front value is smaller
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  // one side still has leftovers, they're already sorted so just append
  return result.concat(left.slice(i)).concat(right.slice(j));
}

// --- Example Usage ---
console.log("mergeSort([5,2,9,1,7,3]):", mergeSort([5, 2, 9, 1, 7, 3]));
// [1,2,3,5,7,9]

// Where this actually matters:
// - Array.prototype.sort() in most engines uses a merge-sort variant
//   (TimSort) because it's STABLE — equal elements keep their relative
//   order, which matters when sorting objects by one field
// - external sorting (sorting data too big to fit in memory, like log
//   files) works exactly like this: sort chunks, then merge them