Heap Sort

Steps:
If we want to sort in ascending then we create a min heap
If we want to create in descending then we create in max heap

Once the heap is created we delete the root node from heap and put the last node in the root position and repeat the steps till we have covered all the elements.
For ascending order:
1. Build Heap
2. Transform the heap into min heap
3. Delete the root node

pseudocode:

source:
http://www.algorithmist.com/index.php/Heap_sort

Implemented code:

output:

Took help from these two links:
http://www.codingeek.com/algorithms/heap-sort-algorithm-explanation-and-implementation/
http://www.geeksforgeeks.org/heap-sort/

Complexity Analysis:
Time Complexity for MaxHeapify: O(logn)
Complexity for BuildHeap: O(n)
Complexity of heapSort:
Worst, Avergae, Base case: O(n*logn)
It is inplace algorithm.
Space Complexity: O(1)