Merge Sort, Step by Step

Merge sort rests on two facts, and both are obvious on their own.

First: an array with one element is already sorted. Second: two sorted arrays can be combined into one sorted array in a single pass, by repeatedly taking the smaller of the two front values.

Put those together and that's the algorithm. Split the array until every piece has one element, which makes them all sorted by definition, then merge pairs back together until there's one array left.

The example we will follow

Everything below traces this array all the way through, live, so you don't have to take any of it on faith:

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

Tracing the recursion

Each call finds the midpoint and splits there, and it never once looks at the values, only the length. That's why merge sort costs the same on sorted, reversed and random input: the shape of this recursion depends only on n.

There's a detail here that trips people up, so it's worth being precise about it. Merge sort does not split everything into single elements and then merge everything back. It's depth-first: it fully finishes the entire left half, all the way down and all the way back up, before it even looks at the right half.

Step through the tree below one call at a time. Watch the call stack panel on the right as much as the tree itself: every frame sitting in it is a paused call, holding onto its left result and waiting on its right one, and that's exactly where the sorted halves live between a split and its merge, not in some array off to the side.

Notice how early the first merge happens. [27,43] merges back together, and then [38] merges with it, before mergeSort([3,9,82,10]) has even been entered. The whole right half of the original array hasn't been touched yet.

That's what depth-first means here, made concrete: the call handling [38,27,43,3,9,82,10] can't merge until both its children have returned, and the left one has to fully resolve, splits and merges and all, before the right one is even called.

The tree is log₂ n levels deep, since each level halves the size. Seven elements gives three levels of splitting, which is also as deep as the call stack ever gets.

The same run in bars

Here's the same algorithm again, but drawn as an array instead of a tree. Step through it and watch the highlighted range narrow as the recursion descends, then widen again as merges complete: that range is exactly the call sitting at the top of the stack in the widget above.

Click a line in the log to jump back.

Inside one merge

The merge is where the actual sorting happens. Take the final merge of [27,38,43] and [3,9,10,82] from the tree above. Both inputs are already sorted, and that's the only thing that makes this work.

Keep a pointer at the front of each side, compare the two values under the pointers, take the smaller, and advance that pointer. Repeat.

Seven elements, six comparisons, one pass. The loop ends the moment either side runs out, and whatever's left on the other side gets copied across wholesale, since it's already sorted and already larger than everything emitted so far.

Step through it yourself here, and switch the operation to see how the same loop answers three other questions:

The one line that decides stability

When the two front values are equal, which side do you take from?

Take from the left. The left half came earlier in the original array, so taking it first preserves the original relative order of equal elements, which is the definition of a stable sort. In code that's the difference between left[i] <= right[j] and left[i] < right[j].

With plain numbers you can't tell the difference, since two equal numbers are indistinguishable. Sort records with equal keys and it matters a great deal, which is why that comparison operator is worth being deliberate about.

The algorithm as a flowchart

A flowchart can't express "call yourself", so what follows is the shape of a single call, with the two recursive steps drawn as ordinary boxes. Click any box with a dot to see what it's for.

The base case is the exit that stops the recursion. Without it, splitting would just keep going forever on empty arrays.

And here's the merge step, which does have a genuine loop:

The dashed copper arrows are the loop: both branches of the comparison rejoin and go back to the "are both sides non-empty" test. Once that test fails, at most one of the two drain steps has anything left to do.

Why it is n log n

Count the work per level rather than per call. At every level of the tree, the merges together touch each of the n elements exactly once, so each level costs O(n). There are log₂ n levels. Multiply and you get O(n log n).

For the example: level 1 merges 7 elements in total, level 2 merges 7, level 3 merges 6. Roughly n per level, three levels.

No input changes this, since the split is positional. That's both merge sort's guarantee and its limitation: it can't exploit input that's already partly sorted, which is exactly the gap Timsort fills by detecting existing runs before it starts.

Where merge sort is the right answer

External sorting. If the data doesn't fit in memory, merge sort still works: sort chunks that do fit, write them to disk, then merge the sorted files by streaming them. The merge only ever needs the front of each run, so it can combine files far larger than RAM.

Linked lists. Merging a linked list needs no extra memory at all, since it's just relinking. Quick sort is awkward on lists because it depends on indexing.

When the worst case matters, quick sort is usually faster but can degrade to O(n²), and merge sort can't.

It's also the basis of Timsort, the default sort in Python, Java for objects, Android, V8 and Swift.

In code

function mergeSort(a) {
  if (a.length <= 1) return a;              // base case: stops the recursion

  const mid = Math.floor(a.length / 2);
  const left = mergeSort(a.slice(0, mid));  // runs to completion first
  const right = mergeSort(a.slice(mid));    // only starts once left returns

  return merge(left, right);
}

function merge(left, right) {
  const out = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    // <= not <: on a tie take the left, which is what keeps this stable.
    if (left[i] <= right[j]) out.push(left[i++]);
    else out.push(right[j++]);
  }

  // At most one of these runs. Whatever is left is already sorted and
  // already larger than everything emitted, so it is copied wholesale.
  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);
  return out;
}

Check yourself