[avocad]

That was a great article! The last paragraph, however:

"By the way, Knuth is interested in these algorithms mainly for the interesting mathematical problems (...) not because they’re in any way efficient algorithms! "

Made me wonder, these kind of algorithms, where there is a lot of comparing and swapping of adjacent records might be more efficient on a tape-based architecture. Or an architecture with a lot of prefetch caching.

[vanderZwan]

Insertion sort is known to be the fastest option for small ranges, which is why it often is the sorting option hybrid sorts switch to for that case (like when the partitions in quicksort or merge sort are small enough).

AFAIK, this is mainly because even though it is expected O(n²), it has a really tiny overhead because insertion sort is incredibly simple, so for small enough n it wins. However, being very cache-friendly is also part of it (it's a linear search over the array).

IIRC some people found similar results for bubble sort.

[steerablesafe]

It's both cache-friendly and its branches are easy to predict.