Heap-sort

The heap-sort algorithm is another in-place sorting algorithm. Heap-sort uses the binary heaps we discussed before. Recall that the BinaryHeap data structure represents a heap using a single array. The heap-sort algorithm converts the input array a into a heap and then repeatedly extracts the minimum value.

More specifically, a heap stores n elements in an array, a, at array locations $a[0],...,a[n − 1]$ with the smallest value stored at the root, a[0]. After transforming a into a BinaryHeap, the heap-sort algorithm repeatedly swaps a[0] and a[n − 1], decrements n, and calls trickleDown(0) so that $a[0],...,a[n − 2]$ once again are a valid heap representation. When this process ends (because $n = 0$) the elements of a are stored in decreasing order, so a is reversed to obtain the final sorted order.

Note: The algorithm could alternatively redefine the compare(x, y) function so that the heap-sort algorithm stores the elements directly in ascending order.

Visual demonstration

The figure below shows an example of the execution of heapSort(a).