3 ms·
That was a great article! The last paragraph, however: "By the way, Knuth is interested in these algorithms mainly for the interesting mathematical problems (.
by avocad 6y ago
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 6y agoInsertion 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 6y agoIt's both cache-friendly and its branches are easy to predict.