Feb. 21, 2014, 4:25 p.m. by Rosalind Team

**Topics**:
Sorting

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

- 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

Return: A sorted array

9 2 6 7 1 3 5 4 8 9

1 2 3 4 5 6 7 8 9

## Running time

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.