Heap-sort

The heap-sort algorithm is another in-place sorting algorithm. Heap-sort uses the binary heaps. 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 a snapshot of the execution of heapSort(a, c). The shaded part of the array is already sorted. The unshaded part is a BinaryHeap. During the next iteration, element 5 will be placed into array location 8.