Feb. 21, 2014, 4:25 p.m. by Rosalind Team
The heap sort algorithm first transforms a given array into a max heap (recall the problem “Building a Heap”).
It then repeats the following two simple steps
Given: A positive integer
Return: A sorted array
9 2 6 7 1 3 5 4 8 9
1 2 3 4 5 6 7 8 9
Transforming a given array into a heap is done in linear time,
$O(n)$. The next stage requires $n-1$"sift-down" operations and hence take time $O(n\log n)$. Hence the overall running time of the heap sort algorithm is $O(n \log n)$.
To see how the heap sort algorithm performs on various types of arrays use the following visualization by David R. Martin: http://www.sorting-algorithms.com/heap-sort. The visualization by David Galles also shows how the heap sort algorithm performs on a random array: http://www.cs.usfca.edu/~galles/visualization/HeapSort.html.