4 ms·
A lot of people look at sorting algorithms with the mental model of a 1970s era PDP-8. They analyze scalar instructions as if they are being executed sequential
by hasmanean 3y ago
A lot of people look at sorting algorithms with the mental model of a 1970s era PDP-8. They analyze scalar instructions as if they are being executed sequentially.
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.
- masklinn 3y agoPer the wiki: > 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.
- kragen 3y agoi think that adaptive time complexity bound holds for both bubble sort with early exit and insertion sort
- kragen 3y agothe vast majority of computers still aren't superscalar, much less ooo; for every i7 there are 100 cortex-m0+s, which don't even have caches. gpus aren't superscalar or ooo either, just heavily multithreaded, simt, and simd 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-bubble-sorts-comeback.html#fallback-for-sorting-short-arrays https://blog.reverberate.org/2020/05/29/hoares-rebuttal-bubb...) which is very surprising to me