Cairn
algorithms · sorting · O(n log n)

↩ back to Comparison Sorts

Merge Sort

Merge sort takes the opposite bet from insertion sort: instead of growing one sorted region by shifting elements into place, it splits the array into halves, sorts each half independently, and then merges the two sorted halves back together in one linear pass. The merge is the whole trick — given two already-sorted lists, you can produce one sorted list by repeatedly taking the smaller of the two fronts, which takes time proportional to their combined length, no comparisons wasted.

Try it

Enter a comma-separated list of numbers, then step through the sort. The dashed box is the active window being merged, split into a left half and a right half (shaded differently); the two highlighted bars are the elements currently being compared. Once a window finishes merging it settles into place and the next, larger window takes over.

Press Load, then Step through the sort.

Why it works

The invariant is on the window, not the whole array: a window of size 1 is trivially sorted. Merging two sorted windows of size w produces one sorted window of size 2w. The demo above sorts this way — bottom-up, doubling the window size each pass (1, then 2, then 4, ...) — rather than the more commonly taught top-down recursive version, because it steps predictably without needing to track a call stack in the visualizer. Both produce identical results; they're the same algorithm viewed from opposite ends.

Reference implementation

The canonical, recursive top-down version — split until you hit single elements, then merge on the way back up:

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 out = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) out.push(left[i++]);
    else out.push(right[j++]);
  }
  while (i < left.length) out.push(left[i++]);
  while (j < right.length) out.push(right[j++]);
  return out;
}

Pitfalls

It's not in-place. Each merge needs somewhere to build its result before copying it back — the recursive version above allocates a new array at every level, and even a careful in-place merge implementation needs O(n) auxiliary space at minimum. This is the direct trade for merge sort's guaranteed O(n log n): insertion sort sorts in O(1) extra space but degrades to O(n²).

Stability, and why <= matters. The merge step takes from the left when the two fronts are equal (left[i] <= right[j]), which keeps elements from the left half ahead of equal elements from the right half — exactly their original relative order, since the left half started to the left of the right half. Flip it to strict < and the sort still produces correct output, but stability breaks, the same subtlety as insertion sort's > versus >=. Measured directly on the reference implementation above: sorting 20,000 random arrays of 40 elements drawn from only 5 distinct keys (so ties are common), the <= version never once lets two equal-keyed elements land out of their original order — 0 of 20,000 trials show a violation. Flip that one comparison to < and every single trial does — 20,000 of 20,000 — with an average of about 35 out-of-order pairs per run. Correctness (did it sort?) and stability (did it preserve tie order?) are different checks, and this one comparison is the entire boundary between them.

"No best case" is true of the growth rate, not the comparison count. Insertion sort runs in O(n) on already-sorted input because its inner loop can bail out early; merge sort has no equivalent early exit, and best, average, and worst case are all genuinely Θ(n log n) here — no input order escapes that class. But "same class" doesn't mean "same number of comparisons," and the actual gap is bigger than that framing suggests. Instrumented the reference implementation above to count every <= comparison it makes: on a sorted or reverse-sorted array of 1,024 elements, every merge exhausts one side before the other is ever touched — the dominant half only ever compares against, never inside, so the count lands on exactly 1024 × log₂(1024) ÷ 2 = 5,120, precisely half of the n log n upper bound. A random permutation of the same 1,024 elements has no such luck and averages 8,947 comparisons across 500 trials (never once dropping below 8,898) — 75% more than the sorted case, though still short of the full 10,240-comparison bound. The reason isn't specific to ascending order: splitting any monotonic run in half — ascending or descending — always yields two halves that don't interleave, so descending input gets the identical 5,120-comparison shortcut for the same reason. Worth separating in general: "no early exit" and "no speed difference by input shape" are different claims, and only the first one holds here.

Complexity

Time: O(n log n) in every case — log n levels of splitting, each level doing O(n) total work across all its merges. That's the recurrence T(n) = 2T(n/2) + O(n), resolved by the Master Theorem — see that guide for the general tool, and Closest Pair of Points and Divide-and-Conquer Convex Hull for two more algorithms landing on the identical bound via the identical shape. Space: O(n) extra for the merge buffers. That guaranteed n log n bound, plus stability, is why merge sort (or a hybrid built on it, like Timsort) backs the stable sort in most standard libraries — Python's list.sort, Java's Arrays.sort for objects, and array merges are the O(log n) backbone behind external sorting, where the data doesn't fit in memory and you're merging pre-sorted chunks read from disk.

For the other classic divide-and-conquer sort, see quicksort — same average-case O(n log n), but it partitions in place instead of merging into buffers, trading merge sort's guaranteed bound for a smaller memory footprint and a worst case that shows up on already-sorted input. See quicksort's own measured comparison for exactly how much that in-place partitioning saves in wall-clock time, despite making more raw comparisons than this page's own merge step. See How Deep Can You Recurse? for why that guaranteed split keeps this page's own recursion safe at any size, unlike quicksort's own worst case.

That n log n bound is actually a theorem about a specific kind of sort — one that only ever asks "is A bigger than B?" Merge sort, insertion sort, quicksort, and heap sort are all built entirely out of such comparisons, so none of them can beat it. Counting sort escapes the bound instead of beating it, by never comparing elements at all — worth reading once this page's guarantee starts to feel like a hard floor rather than one strategy's tradeoff.

See Choosing a Comparison Sort for how merge sort's stability and guaranteed bound stack up against the other eleven comparison sorts on this site.