One iteration of bubble sort is: find two elements in the wrong order and swap them.

One iteration of insertion sort is: find an element out of order, then find the location in the array where it should've been, then move all the items between those two slots one slot ahead, then insert the out-of-order element into the now free slot where it belongs.

Admittedly, insertion sort is pretty intuitive, since it reflects more or less how a human would instinctively try to sort a list; take an out-of-order element and move it to where it belongs. But when translated to code, I think it's very hard to beat "find two items in the wrong order and swap them".

Once you admit superscalar execution (multiple loadstore pipes), out of order execution and caches into the picture ( as well as the possibility of almost sorted arrays as input) the picture is never as simple.

That said, I’m curious whether insertion sort is categorically better than bubble sort. I thought they might have been equivalent for the almost sorted case. I’ve heard both sides argued on this thread.

> Adaptive, i.e., efficient for data sets that are already substantially sorted: the time complexity is O(kn) when each element in the input is no more than k places away from its sorted position

In fact it’s often a sub-sort of hybrid sorts, like timsort:

> If a run is smaller than this minimum run size, insertion sort is used to add more elements to the run until the minimum run size is reached.

even if insertion sort reliably beats bubble sort on your ssd ftl chip and your wristwatch, though, it seems like there are cases on modern high-performance hardware where insertion sort is worse than bubble sort (cf. https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubb...) which is very surprising to me

Eg Rust has no-std crates that you can use even if you can't use the standard library.

And given that C's stdlib has a quicksort function, how would using a different language have helped?

commonly (as in wellons's post about the two-sum problem) there's a variation on the standard algorithm that can help significantly, but which the standard library function doesn't have an option for

also i think the cost of reimplementing simple 'algorithms from the book' like insertion sort or even quicksort is pretty low; as you saw in my comment above, insertion sort is six lines of code and only moderately bug-prone. we aren't talking about fibonacci heaps or red-black trees or fm-indexes or rader's algorithm or something. the cost is low enough that it's easy to justify in a lot of cases

I can never remember the loop bounds of bubble sort, always have to look it up.

That said a lot of time I have small arrays of objects. Instead of keeping them sorted I just grind through them to find the next largest value. That tends to be hard to get wrong.