In computer science, adaptive heap sort is a comparison-based sorting algorithm of the adaptive sort family. It is a variant of heap sort that performs better when the data contains existing order. Published by Christos Levcopoulos and Ola Petersson in 1992, the algorithm utilizes a new measure of presortedness, Osc, as the number of oscillations. Instead of putting all the data into the heap as the traditional heap sort did, adaptive heap sort only take part of the data into the heap so that the run time will reduce significantly when the presortedness of the data is high. Heapsort Heap sort is a sorting algorithm that utilizes binary heap data structure. The method treats an array as a complete binary tree and builds up a Max-Heap/Min-Heap to achieve sorting. It usually involves the following four steps. Build a Max-Heap(Min-Heap): put all the data into the heap so that all nodes are either greater than or equal (less than or equal to for Min-Heap) to each of its child nodes. Swap the first element of the heap with the last element of the heap. Remove the last element from the heap and put it at the end of the list. Adjust the heap so that the first element ends up at the right place in the heap. Repeat Step 2 and 3 until the heap has only one element. Put this last element at the end of the list and output the list. The data in the list will be sorted. Below is a C/C++ implementation that builds up a Max-Heap and sorts the array after the heap is built. /* A C/C++ sample heap sort code that sort an array to an increasing order */ // A function that build up a max-heap binary tree void heapify(int array[], int start, int end) { int parent = start; int child = parent * 2 + 1; while (child <= end) { if (child + 1 <= end) // when there are two child nodes { if (array[child + 1] > array[child]) { child ++; //take the bigger child node } } if (array[parent] > array[child]) { return; //if the parent node is greater, then it's already heapified } if (array[parent] < array[child]) // when child node is greater than parent node { swap (array[parent], array[child]); // switch parent and child node parent = child; child = child * 2 + 1;