Merge Sort

How it works, step by step

1. 1

   Split the array into two halves. Keep splitting each half until every piece has just one value - a single value is already sorted.

2. 2

   Merge pieces back together in pairs: compare the first value of each piece, take the smaller one, repeat until both pieces are empty.

3. 3

   Each merged pair is a sorted run twice as long as before.

4. 4

   Keep merging: runs of 1 become runs of 2, then 4, then 8...

5. 5

   After about log n rounds, one run covers the whole array - and it is sorted.

6. 6

   Every round touches each value once, so the total work is n × log n.

The code, in JavaScript

function mergeSort(arr) {
  if (arr.length <= 1) return arr;      // one value = already sorted

  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 out = [];
  let i = 0, j = 0;

  // Take the smaller head, again and again.
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) out.push(left[i++]);
    else out.push(right[j++]);
  }

  // One side ran out - the rest of the other side is already sorted.
  return [...out, ...left.slice(i), ...right.slice(j)];
}

mergeSort([5, 1, 4, 2]);               // → [1, 2, 4, 5]

Dry run: sorting [5, 1, 4, 2]

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• The merge must use `<=`, not `<`, when taking from the left run. With `<`, equal values from the right run jump ahead - and the sort silently stops being stable.
• Forgetting the leftover copy (`...left.slice(i), ...right.slice(j)`) is the classic bug: the code works on most inputs and quietly drops values when one run empties early.
• `arr.slice(mid)` everywhere makes many copies. Fine for learning; production versions merge inside one shared temp buffer instead of allocating per call.
• Merge sort's O(n log n) is a worst-case guarantee, but its best case is also O(n log n) - on nearly-sorted data, insertion sort or TimSort (which detects sorted runs) is faster.

Merge Sort vs. its closest relatives