Problem

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 $n-1$ times:

• Swap the last element of the heap with its root and decrease the size of the heap by $1$.
• "Sift-down" the new root element to its proper place.

Given: A positive integer $n \le 10^5$ and an array $A[1..n]$ of integers from $-10^5$ to $10^5$.

Return: A sorted array $A$.

Sample Dataset

9
2 6 7 1 3 5 4 8 9

Sample Output

1 2 3 4 5 6 7 8 9

Running timeclick to expand

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)$.

Visualization

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.