. For adaptive heap sort, instead of putting all the elements into the heap, only the possible maximums of the data (max-candidates) will be put into the heap so that fewer runs are required when each time we try to locate the maximum (or minimum). First, a Cartesian tree is built from the input in time by putting the data into a binary tree and making each node in the tree is greater(or smaller) than all its children nodes, and the root of the Cartesian tree is inserted into an empty binary heap. Then repeatedly extract the maximum from the binary heap, retrieve the maximum in the Cartesian tree, and add its left and right children (if any) which are themselves Cartesian trees, to the binary heap. If the input is already nearly sorted, the Cartesian trees will be very unbalanced, with few nodes having left and right children, resulting in the binary heap remaining small, and allowing the algorithm to sort more quickly than for inputs that are already nearly sorted. Below is an implementation in pseudo-code: Input: an array of n elements that need to be sorted Construct the Cartesian tree l(x) Insert the root of l(x) into a heap for i = from 1 to n { Perform ExtractMax on the heap if the max element extracted has any children in l(x) { retrieve the children in l(x) insert the children element into the heap } } Drawbacks Despite decades of research, there's still a gap between the theory of adaptive heap sort and its practical use. Because the algorithm makes use of Cartesian trees and pointer manipulation, it has low cache-efficiency and high memory requirements, both of which deteriorate the performance of implementations. See also Adaptive sort Heapsort Cartesian tree References Sorting algorithms Comparison sorts Heaps (data structures)