If a list is already close to sorted, according to some measure of sortedness, the number of comparisons required to sort it can be smaller. An adaptive sort takes advantage of this "presortedness" and runs more quickly on nearly-sorted inputs, often while still maintaining an O ( n log ⁡ n ) {\displaystyle O(n\log n)} worst case time bound. An example is adaptive heap sort, a sorting algorithm based on Cartesian trees.