How does merge sort work
Last time we sorted a line by comparing neighbors and sending the bigger one back. It works, but when the line gets long, it's far too slow, because the more cards there are, the more comparisons pile up. Is there a smarter way? Yes: split the line in half.
One at a time is slow
The last method was nice because it was simple: compare neighbors and send the bigger one back.
But as the line grows, there's far too much comparing to do.
Double the cards and the comparisons jump four times. Four cards is quick, but thirty-two feels endless.
Double the line. Twice the length → four times the comparisons.
The bars shoot up alarmingly.
The longer the line, the worse the slowness gets.
The problem is treating the whole line as one lump and comparing all the way through.
So what if we split the lump?
Split it in half
Instead of handling the long line whole, split it in half.
Split each half in half again, and again, and in the end only single cells are left.
And a single cell is already sorted, because it's alone and has nothing to compare with.
Keep splitting one group in half. 8 → 4+4 → 2+2+2+2 → one cell each.
Is splitting the end of it?
No. What you split has to be gathered back into a line: pair up the single cells and merge them, then merge those merged groups again.
And merging two sorted groups turns out to be surprisingly easy.
Merge two sorted groups
The secret to merging two sorted groups into one line is to look only at the front.
Compare the first cell of each group and drop the smaller one into the result. The next cell takes its place, and you compare the first cells again.
They mesh together one cell at a time, like a zipper closing.
Compare the fronts of the two groups and drop the smaller one. Merge one cell at a time, like a zipper.
Isn't that interesting? Comparing across the whole jumbled line was slow, but merging two groups that are each already sorted is fast, because you only look at the front.
Splitting creates small sorted pieces, and merging them back step by step soon gives you a complete line.
Why it's fast: the number of levels
Why is this faster?
Because you split in half, there aren't many levels of splitting. Even when the line doubles, the number of levels grows by just one.
Merging one level costs about the length of the line, so the total cost is the number of levels times the line length.
That grows far more slowly than comparing one at a time (length times length).
Unfold the levels and change the line length. Levels x one level = grows more slowly than one at a time.
You'll learn the exact formula later.
For now, just take away the feeling: splitting in half makes the levels grow slowly, and each level merges lightly, so the whole thing speeds up.
This one move of splitting and merging changes the speed dramatically.
Summing up
Put together in one thread, it goes like this.
Sorting by comparing one at a time gets slower as the line gets longer.
So you split the line in half and keep splitting until you get single cells, which are already sorted pieces.
Merge those sorted pairs like a zipper, and since you only merge as many times as there are levels, the whole line falls into place much faster.
Split and merge: that's the heart of smarter sorting.
Press the four steps in turn and follow one full round. Split → single cell → merge → only as many levels as needed = fast.
Here we always split calmly down the middle.
But there's a cousin that picks the dividing point a little differently: instead of the middle, it chooses one cell as a pivot and divides the rest into smaller and bigger.
How to pick that pivot is a story for later.
For today, just take this away: split in half and merge, and things get faster.