Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re...
by masklinn on Monday August 21, 2023 @04:24PM
(#37214878)
Per 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.
Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re...
by kragen on Tuesday August 22, 2023 @12:40AM
(#37218769)
i think that adaptive time complexity bound holds for both bubble sort with early exit and insertion sort
Re:FreeBSD replaces bubblesort with mergesort on SYSINTs, re...
by kragen on Monday August 21, 2023 @10:36PM
(#37217954)
the 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-bubb...) which is very surprising to me
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.