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 n

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.