Heap Sort is a comparison based sorting algorithm.
It partitions the array into sorted and unsorted partitions.
It builds a Max Heap of unsorted partition.
At every iteration, it extracts the maximum element from Heap and move it to the sorted partition.
This operation is repeated until all the elements are sorted.
It has best, average and worst case complexity of O(n log n).