Inversions. Using this measure of presortedness – being relative to the number of inversions – Straight Insertion Sort takes less time to sort the closer it is to being sorted. Other examples of adaptive sorting algorithms are adaptive heap sort, adaptive merge sort, patience sort, Shellsort, smoothsort, splaysort, Timsort, and Cartesian tree sorting. See also Sorting algorithms Smoothsort References Sorting algorithms