Sorting the smarter way

One by one is slow

Last time's way was nice and simple.
Compare neighbors, bigger one back.
But as the line grows long,
there's just too much to compare.
Double the cards,
and the comparisons jump fourfold.
Four is quick,
but thirty-two is a long haul.

Try doubling the line. (Length doubles → comparisons leap fourfold)

The bar fills up alarmingly.
The longer the line,
the worse the slowness gets.
The trouble is treating
the whole line as one lump
and comparing to the end.
So what if we
break the lump apart?

Split it in half

Don't handle the long line whole.
Split it in half.
That half in half again,
and that half in half too.
Keep splitting,
and at the end only singles remain.
But a single
is already sorted.
Alone, there's nothing to compare.

Keep halving one group. (8 → 4+4 → 2+2+2+2 → singles)

Is splitting the whole job?
No, the split pieces
must come back together to make a line.
Pair the singles
and merge them two by two,
then merge those again.
And merging two sorted pieces
turns out to be surprisingly easy.
Let's see next.

Merge two sorted ones

We have two sorted groups.
To merge them into one line,
the trick is to look only at the fronts.
Compare the first card of each,
drop the smaller into the result.
The next card fills that slot,
and you compare fronts again.
Like closing a zipper,
they mesh together one notch at a time.

Compare the fronts of the two groups, drop the smaller. (Merge one notch at a time, like a zipper)

Isn't it neat?
Comparing a whole jumble was slow,
but merging two already-sorted ones
is fast, since you only watch the fronts.
Thanks to splitting,
we get small, sorted pieces,
and merging them up bit by bit
becomes a whole line before you know it.

Why it's fast: the number of layers

Why is this faster?
Because we halve,
there aren't many splitting layers.
Double the line,
and the layers grow by just one.
And merging one layer
costs about the line's length.
So the total cost is
layers times line length.
That grows far slower
than one by one (length times length).

Reveal layers and change the line length. (Layers x per layer grows slower than one by one)

The exact formula comes later.
For now, just take the feel.
When you halve,
the layers grow sluggishly,
and each layer merges lightly,
so the whole thing speeds up.
This one move, split and merge,
changes the speed dramatically.

Let's wrap up

Threaded on one line, it goes like this.
Sorting by comparing one by one
is slow as the line grows.
So we split the line in half,
and split all the way to singles,
which are pieces already sorted.
Merge those sorted ones like a zipper,
and with only as many merges as layers,
the whole line falls into order much faster.
Split and merge.
That's the heart of smart sorting.

Tap the four steps in order to follow one loop. (Split → singles → merge → layers only = fast)

Here, merging always split calmly in half.
But there's a cousin
that picks its dividing point a bit differently.
Instead of the middle,
it takes one card as a marker
and splits into smaller and bigger.
How to choose that marker
I'll leave for a later story.
For today, just carry this:
split in half and merge, and it gets fast.