2D insertion sort. Implementation.
In the previous post I described a nice 2D array sorting approach based on insertion sort. Today you can see how it behaves in practice — watch the video. I personally love this kind of algorithm visualization.
Just watching the drone already gives a couple of insights. It doesn’t always travel far from the insertion point — and that’s the key property of insertion sort: the work depends not only on n, but also on how “sorted” the data already is. So an almost-sorted field gets fixed surprisingly fast.
Now compare it with two other classic quadratic algorithms.
Selection sort and bubble sort don’t really care what’s inside — they keep scanning the whole unsorted part anyway. That’s why their basic “effort budget” is always about n·(n−1)/2 comparisons, no matter how lucky the input is.
And here we have a nice bridge from “toy programming” in The Farmer Was Replaced to serious computer science.
A famous real-world trick: quicksort is great, but deep recursion and tiny partitions are expensive. So many implementations stop quicksort early, leaving the array only almost sorted — and then run insertion sort as a final polish pass.