Merge Sort, All the Way Down: The Code, the Proof, and One Full Trace

Ask for a sorting algorithm and you get seven lines of code: split, sort the halves, merge them back. That alone sounds logarithmic — so where does the extra factor of n hide, and why does it hide there? This video is merge sort all the way down: the code, the correctness proof, the recurrence solved, and one complete run traced start to finish.

One algorithm, three questions: What do the seven lines actually say? Why does the answer come out sorted — guaranteed, not just observed? And where exactly does the n log n come from?

Part one — the algorithm. Two moves, only two: split the array in half, sort the halves, merge them back. Merge is where the algorithm pays for its guarantee — two sorted lists, one pointer at the front of each, always compare the heads, copy the smaller one out, advance that pointer, and when one list empties, dump the rest of the other. Every element moves exactly once: a single linear pass, cn, that everything downstream charges to. The pointers never back up — division going down the tree, merging coming back up, both one-way.

Part two — correctness. Two claims, earned in order. Claim one: given two sorted inputs, merge produces a sorted output — proved as a loop invariant (after k picks, the output holds the k smallest elements across both inputs, in order). Claim two: merge sort correctly sorts any array — proved by induction on length, with claim one doing the work of the inductive step. Then the runtime: T(n) = 2T(n/2) + cn, unrolled on a recursion tree with log₂n levels, each level costing cn — total cn·log n. That's where the extra factor hides: not in the depth, in what happens at every depth.

Part three — one complete run, nothing skipped. Eight values, three levels, seven merges, every compare counted as it fires — watch the recursion split all the way down, then the merges climb back up, and check that the total work lands exactly on n·log n. Proved, not promised.

⏱️ Chapters 0:00 – Introduction: seven lines, one hidden factor of n 0:29 – Part 1: The algorithm — split, sort, merge 0:44 – The merge operation everything charges to 1:03 – The recursion: two calls, one linear merge 1:54 – Part 2: Correctness — the merge invariant 2:11 – Claim two: induction on array length 2:53 – The recurrence T(n) = 2T(n/2) + cn 3:08 – Unrolling the recurrence with the recursion tree 3:34 – Part 3: A full trace — eight values, three levels 4:02 – Merges climbing back up, compare by compare 5:07 – Total work matches n·log n — proved not promised 5:18 – Verdict 5:37 – Your turn: trace it yourself

💬 Your turn — paste this into Claude: "Run merge sort on this array: [9, 3, 7, 1, 8, 4, 6, 2]. Before you run it, help me predict the total number of compares by counting per level. Then trace every merge step by step so I can check my prediction. If it doesn't match, find the merge where my count was off."

🔔 Subscribe for more algorithms proved and traced, one recurrence at a time.

Hashtags

Keywords / tags (comma-separated for YouTube tags field)

merge sort, merge sort explained, merge sort algorithm, big O notation, n log n, divide and conquer, sorting algorithms, algorithm proof, loop invariant, proof by induction, recursion tree, recurrence relation, time complexity analysis, computer science education, coding interview prep, data structures and algorithms, algorithm correctness proof, merge sort trace, T(n) = 2T(n/2) + cn, CS fundamentals, learn algorithms, Claude AI coding

Transcript

A lightly formatted transcript of the video, with timestamps so you can jump to any section on YouTube.

[0:00] Malwinny, this is Liam in for Bear. Ask for sorting algorithm and you get seven lines of code. Have have have then merge back up that alone sounds logarithmic. So, where does the extra factor of n hide and why does it hide there? This is merge sort all the way down. The code, the correctness, the recurrence solved in one complete run. Here is the whole plan typed slowly. One algorithm, three questions. What do the seven lines actually say? Why does the answer come out sorted, not observed, guaranteed? And where exactly does the n log n live? Part one, the algorithm. Two moves and only two. Split the array in half, sort

[0:33] The halves, then merge them back. The whole trick lies in what merge does because merge is where the algorithm actually pays for its guarantee. First, the one operation everything hangs on. Two already sorted lists, one pointer at the front of each. Compare the heads, copy the smaller one out, advance that pointer. Repeat. When one list empties, dump the rest of the other. Every element moves exactly once. That is a single linear pass, the c times n that everything downstream is going to charge to. Now, the top half merge sort itself. If the array is trivial, one element or none, it is already sorted, return. Otherwise, split at the middle, sort

[1:07] Each half by calling the same function, and merge the two sorted results back together. Two recursive calls, one linear merge. That is the entire recursion. In the bottom half merge, three pointers, one into each sorted input, one into the output. While both inputs still have material, take whichever head is smaller and advance that pointer. When one runs out, splice the remainder of the other on. Notice what never happens. The pointers never back up. Two directions, both one way. Hold on to that. Every recursive call spawns two more until the pieces are size one, which are already sorted for free. Then the calls unwind, merging pairs of

[1:42] Ones into twos, twos into fours, fours into the whole. Down the tree is division, up the tree is merging. Two arrows, both one way. Every proof in part two is just these arrows cashed in. Part two, correctness. Two claims to earn in order. First, given two sorted inputs, merge produces a sorted output. Then, on top of that, merge sort correctly sorts any array. The first is an invariant on the merge loop. The second is induction, and its inductive step is exactly the first claim. Claim one, the merge invariant. After K picks, the output holds the K smallest elements across both inputs, and they sit in

[2:14] Sorted order. Initialization, K equals zero, output is empty, trivially true. Maintenance, at each step, you copy the smaller of the two heads. Every element still unpicked is at least as large as the one you just copied. Termination, when both inputs empty, K equals the total, and the invariant says the whole output is sorted. Claim two, merge sort itself by induction on the length of the array. Base case, length zero or one, already sorted, and the code returns immediately. Inductive step, assume merge sort correctly sorts any array shorter than N. Then, on an input of length N, the two recursive calls each sort a shorter half. That is the

[2:46] Inductive hypothesis discharged. Merge then takes two sorted inputs, and by claim one, hands back one sorted output. Induction closes. Now, the run time, write the cost as a recurrence. T of N is the two recursive halves, 2 T of N over 2, plus the merge, which we saw was C times N. So, T of N equals 2 T of N over 2 plus CN. This one line hides the whole answer, but only if you unroll it, which is exactly what the tree does for you. Now, the tree does the unrolling. At the top, one merge of size N costs CN. Level down, two merges of size N

[3:17] Over 2, total cost CN. Level down again, four of size N over 4, total CN. Every level costs the same CN, and the tree has log 2 of N levels before hitting size one. Total work, CN times log N. That is where the extra N hid, not in the depth, in what happens at every depth. Part three, one complete run, nothing skipped. Eight values, three levels, seven merges. Watch exactly two things, the recursion splitting the array all the way down, then the merges climbing back up, and count the compares as they fire. The instance, eight values, 5 2 8 1 6 3 7 4, not sorted, not reversed, and every

[3:50] Pair contested when it meets its neighbor. Split at the middle, left half 5 2 8 1, right half 6 3 7 4. Split again and again until the leaves are size one, which are sorted for free. Now merge back up. Leaves are pairs of ones, so each merge takes exactly one compare. Five against two, two goes first. Eight against one, one goes first. Six against three, three goes first. Seven against four, four goes first. Four merges, four compares, and the level below is now four sorted pairs. Level one, two sorted pairs meet. 2 5 with 1 8. One comes first, then two beats five, then five slides in ahead of

[4:24] Eight, then eight tails. Three compares, four cells moved. On the right, 3 6 with 4 7. 3 4 6 7. Again, three compares. Two merges, six compares, and the level again touched all eight elements. The root 1 2 5 8 against 3 4 6 7. One first, free, no compare against the other side yet. Then one against three, one wins. Two against three, two wins. Now five against three, three wins. Five against four, four wins. Five against six, five wins. Six wins over eight, seven wins over eight, eight tails in. Seven compares to now leave eight elements, the biggest single merge in the whole run. Now read the result back through

[4:58] The tree. Three levels of merging, the leaves at depth two, the pairs at depth one, the root at depth zero. Every level moved all eight elements. Three levels times n work equals 3n. Log two of eight is three, so the total work went as n times log n, exactly as the recurrence predicted. Not luck, the tree cashed in. The verdict, seven lines of code, split in half, sort the halves, merge them back. Merge is a linear two-pointer scan. It's invariant says the output holds the smallest pick so far in order. Induction on length lifts that to the whole array. The recurrence T of n equals 2 T of n over 2 plus c n unrolls

[5:30] On a tree of log n levels, each level doing c times n work, total c times n log n. Proved, not promised. Your turn. Open a Claude session and paste this. Run merge a sort on the array in the description, eight values different from mine. Before you run it, predict the total number of compares by counting per level. Then trace every merge and check that your prediction matches. If it does not, find the merge where your count was off. That is where the recurrence hit a constant you missed. The full prompt is in the description. Merge sort proved and traced. Now you know, lie 'em in for

[5:59] Bear.