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:

Heapsort(A as array)
    BuildHeap(A)
    for i = n to 1
        swap(A[1], A[i])
        n = n - 1
        Heapify(A, 1)

BuildHeap(A as array)
    n = elements_in(A)
    for i = floor(n/2) to 1
        Heapify(A,i,n)

Heapify(A as array, i as int, n as int)
    left = 2i
    right = 2i+1

    if (left <= n) and (A[left] > A[i])
        max = left
    else 
        max = i

    if (right<=n) and (A[right] > A[max])
        max = right

    if (max != i)
        swap(A[i], A[max])
        Heapify(A, max)

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

Implemented code:

//this is descending order max-heapify

#include<bits/stdc++.h>
using namespace std;
//swapping numbers using call by reference
int swaps(int *p,int *q)
{
    int temp=*q;
    *q=*p;
    *p=temp;
}

//this max heapify ensure that child node is always smaller than the parent node
MaxHeapify(int ary[],int n,int i){
    int largest=i;
int    left=2*i+1;
int     right=2*i+2;
    if(left<n && ary[left]>ary[largest])
    {
        largest=left;
    }
    if(right<n && ary[right]>ary[largest])
    {
        largest=right;
    }
    if(largest!=i)
    {
        swaps(&ary[i],&ary[largest]);
        MaxHeapify(ary,n,largest);
    }
}

//building heap
void BuildHeap(int ary[],int n)
{
    int i;
    for(i=floor(n/2)-1;i>=0;i--){
        MaxHeapify(ary,n,i);
    }
}

//heapSort function sorting the array
void heapSort(int ary[],int n)
{
    BuildHeap(ary,n);
    for(int i=n-1;i>0;i--){
           swaps(&ary[0],&ary[i]);
           int heap_size=i;
           MaxHeapify(ary,heap_size,0);
    }
}
//utility function
void printAry(int ary[],int n)
{
    for(int i=0;i<n;i++)
    {
        cout<<ary[i]<<" ";
    }
}
//driver program
int main(){
    int ary[]={40,60,10,20,50,30};
    int n=sizeof(ary)/sizeof(ary[0]);
    heapSort(ary,n);
    cout<<"Sorted array:";
    printAry(ary,n);

}

output:

Sorted array:10 20 30 40 50 60

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)