Loading transcript…
01
The problem we're trying to solve
00:04
Suppose you have a long list of numbers, scattered in no particular order, and you'd like them sorted from smallest to largest.
00:14
There are many ways to do this. Most of them are slow in ways that aren't obvious. One of them — merge sort — is fast in a way that's worth understanding.
02
Divide and conquer
00:52
The trick is this: sorting a list of eight numbers feels hard. Sorting a list of two numbers feels trivial. Can we get from the hard problem to the easy one by cutting?
01:08
Cut the list in half. Cut each half in half. Keep going until each piece is one number, which is already sorted by definition — there's nothing to sort.
we only recurse once per level — that's the whole log-n story.
03
Base case
01:56
A list of one thing is sorted. This feels like a cheat, but it's the foundation the whole algorithm rests on.
04
The merge step
02:27
Now — suppose I hand you two lists that are each already sorted, and I ask you to combine them into one sorted list. How would you do it?
02:41
Walk down both at once. Put a finger on the first element of each. Whichever finger is pointing at the smaller number — that's the next one in your output. Advance that finger. Repeat.
03:04
When a finger runs off the end of its list, the rest of the other list simply tips into the output — it was already sorted, so there's no more work to do.
this is the whole "clever" part. everything else is just recursion.
05
Why log(n) levels
04:10
Every time we cut, the lists get half as long. If we start with 1,024 numbers, we halve ten times before hitting pieces of size one — because two to the tenth is 1,024.