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²).

Three of those properties have consequences you will measure: stability in steps 5 and 6, the pivot in step 7.

What stays the same as lesson 7

The skeleton in the panel, the algorithms in prose and pseudocode, the test as the verdict. dcsort.go will be yours.