Skip to content

level 3 · Sorting

Merge Sort

Split until it's trivial, then merge back in order.

12 min 90 XP

what is it

Start here

Here is a strange idea that turns out to be brilliant: don't sort the list. Cut it in half. Then cut those in half. Keep cutting until every piece is a single item — and a single item is *already sorted*, for free.

Now the real work: merging. Take two sorted piles and combine them into one sorted pile. That's easy — just keep taking whichever front item is smaller. You never look back, and you never compare anything twice.

Merge sort is the first algorithm here that is genuinely fast. Splitting takes about log n rounds, and each round merges n items — so the cost is n log n. On a million items that's roughly 20 million steps instead of bubble sort's 500 billion. And unlike bubble or selection, it is fast in the *worst* case, not just on average.

real-life analogy

Picture it

Two people merging sorted piles of exam papers

You each have a pile of papers, already sorted by name. To combine them, you both look at your top paper, and whoever has the earlier name puts theirs down. Repeat. You never re-read the piles, never shuffle, never go back — one clean pass and the two piles are one.

interactive visualization

Watch it run

Watch the list break apart into single items, then rebuild in order.

  1. 8
  2. 3
  3. 5
  4. 1
  5. 9
  6. 2
  7. 7

Merge sort splits the list in half, over and over, until every piece is a single item. A single item is already sorted — then it merges the pieces back together in order.

step 01/61

  • comparing
  • moving
  • in final place
1function mergeSort(a, lo = 0, hi = a.length - 1) {
2 if (lo >= hi) return a;
3 const mid = Math.floor((lo + hi) / 2);
4 mergeSort(a, lo, mid);
5 mergeSort(a, mid + 1, hi);
6 merge(a, lo, mid, hi);
7 return a;
8}
9
10function merge(a, lo, mid, hi) {
11 const left = a.slice(lo, mid + 1);
12 const right = a.slice(mid + 1, hi + 1);
13 let i = 0, j = 0, k = lo;
14 while (i < left.length && j < right.length) {
15 if (left[i] <= right[j]) a[k++] = left[i++];
16 else a[k++] = right[j++];
17 }
18 while (i < left.length) a[k++] = left[i++];
19 while (j < right.length) a[k++] = right[j++];
20}

variables right now

Nothing in play yet — press play.

comparisons 0moves 0

the dry run · every step, in words

61 steps

complexity

What it costs

best case
O(n log n)
average
O(n log n)
worst case
O(n log n)
extra memory
O(n)

Same speed on the best day and the worst day — nothing about the input can hurt it. The price is memory: it needs a second array to merge into, so it is not O(1) space like the simple sorts.

  • O(1)
  • O(log n)
  • O(n)
  • O(n log n) · this one
  • O(n²)
input size →work →

common mistakes

Common traps

  • Forgetting the base case.

    A piece of one item must return immediately. Without that, the splitting never stops and the call stack overflows.

  • Losing the leftovers after the merge loop ends.

    One half always runs out first. The rest of the other half is already sorted — you must still copy it over, or those values vanish.

  • Using `<` instead of `<=` when comparing the two fronts.

    With `<`, equal values swap their original order. That makes the sort unstable, which quietly breaks anything that was sorted by a second key first.

  • Assuming n log n is 'a bit better' than n².

    On a million items it is the difference between 20 million steps and 500 billion — seconds versus days. It is not a small win.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+90 XP

01Why is a single item 'already sorted'?

02What is merge sort's worst-case time?

03What does merge sort pay that bubble sort doesn't?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.