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.
> 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.