So far it has looked simple: O(n²) is bad, a minute and a half is a long time, and next lesson you will learn to do better.

Now change the order instead of the algorithm.

Already-sorted data

$ algo sort -in s10k.jsonl -order sorted
n = 10000, order = sorted

algorithm         comparisons            swaps         wall
bubble                   9999                0           0s
selection            49995000                0    160.053ms
insertion                9999                0           0s

Insertion sort: 9,999 comparisons instead of 24,893,296. Two and a half thousand times fewer. The clock reads 0s, because there is so little work that it cannot see it — lesson 1, the same effect.

Bubble sort with its swapped flag does exactly the same.

And selection sort does 50 million comparisons, precisely as many as on scattered data. It never noticed there was no work to do. That is what "has no best case" means.

Nearly sorted — the realistic case

Perfectly sorted data is artificial. More realistic: data that was sorted and then changed a little. Swap 1% of the positions:

$ algo sort -in s10k.jsonl -order nearly
n = 10000, order = nearly

algorithm         comparisons            swaps         wall
bubble               49744722           632652    212.425ms
selection            49995000              100    157.292ms
insertion              642651           632652      1.491ms

1.5 milliseconds against 212 and 157. A hundred times faster than either of the others — and it is the same algorithm that took 92 ms a moment ago.

One percent of disorder, and insertion sort is still very nearly linear.

The worst case

$ algo sort -in s10k.jsonl -order reverse
n = 10000, order = reverse

algorithm         comparisons            swaps         wall
bubble               49995000         49995000    379.949ms
selection            49995000             5000    167.647ms
insertion            49995000         49995000    180.245ms

Reverse-sorted input, and all three do exactly n(n−1)/2 comparisons. Insertion sort's advantage disappears completely.

One algorithm, three orders, three entirely different outcomes:

insertion sort	comparisons	wall
sorted (best)	9,999	0 s
nearly sorted	642,651	1.5 ms
shuffled (average)	24,893,296	92 ms
reverse (worst)	49,995,000	180 ms

In lesson 1, best/average/worst was a definition. Now it is four numbers from your own program, and the extremes are five thousand times apart.

So where is the use in that

The obvious objection: if the data is already sorted, why sort it?

Because data is rarely "sorted" or "not". It is usually nearly sorted: you appended ten new items to a million, updated a few ratings, merged two almost-tidy lists.

Insertion sort is close to linear on exactly that, and the other two are not.