Lesson 7 ended with a minute and a half of bubble sort on a hundred thousand items — and one result you did not expect: insertion sort beat everything on nearly-ordered data.

This lesson changes the method itself. From O(n²) to O(n log n), and on the same hundred thousand items the difference is two hundredfold.

Why log n

Halve the slice, halve it again, again — how many times until the pieces are single items? log₂ n times. For 100,000 items, seventeen splits.

At each level all n elements are handled, so the total work is n·log₂ n. For a hundred thousand that is about 1.7 million instead of five billion.

It is the same number you met in lesson 6: binary search found an item in 17 comparisons because 2¹⁷ > 100,000. The same bound, a different use.

What you will build

Two algorithms, and they differ more than they look:

• merge sort — stable, no bad case, but it needs a second array;
• quicksort — in place, usually faster, unstable, and with the wrong pivot it falls back to O(n²).

These properties have consequences you will measure: stability in steps 6 and 7, the pivot in step 8.

The lesson climbs in steps

As in lesson 7, you do not start from an empty panic("not implemented"). The skeleton is in the panel and the test is the verdict, and the rungs are the same, only higher:

1. Watch. Eight numbers, two algorithms, every step written out in a table. You write nothing.
2. Fill the holes. Merge sort arrives with its recursion and loops already written. Two places are missing — one of them the single character where stability lives.
3. Write it yourself. Partitioning and three quicksort variants — empty skeletons.

Only then do you measure — and only then do you see what your code does to sorted data.