Comparison-based sorting algorithms have traditionally dealt with achieving an optimal bound of
O(
n log
n) when dealing with
time complexity. Adaptive sort takes advantage of the existing order of the input to try to achieve better times, so that the time taken by the algorithm to sort is a smoothly growing function of the size of the sequence
and the disorder in the sequence. In other words, the more presorted the input is, the faster it should be sorted. This is an attractive feature for a sorting algorithm because sequences that nearly sorted are common in practice. Thus, the performance of existing sorting algorithms can be improved by taking into account the existing order in the input. Most worst-case sorting algorithms that do optimally well in the worst-case, notably
heap sort and
merge sort, do not take existing order within their input into account, although this deficiency is easily rectified in the case of
merge sort by checking if the last element of the left-hand group is less than (or equal) to the first element of the righthand group, in which case a merge operation may be replaced by simple concatenation – a modification that is well within the scope of making an algorithm adaptive. == Examples ==