******* HEAP SORT ******* 

sift(A, l, r)
-------------
f <- l
s <- 2 * l
temp <- A[f]
found <- false
while not found and s <= r
    if s < r and A[s-1] < A[s] then
        s <- s+1
    if temp >= A[s-1] then
        found <- true
    else
        A[f-1] <- A[s-1]
        f <- s
        s <- 2 * f
A[f-1] <- temp


heapsort(A,N)
-------------
l <- N / 2 + 1
r <- N
while l > 1
    l <- l - 1
    sift(A, l, r)
while r > 1
    temp <- A[0]
    A[0] <- A[r-1]
    A[r-1] <- temp
    r <- r - 1

:~~~~~ Average case performance: O(23N Ln N)
:~~~~~ Worst case performance:   O(26N Ln N)

A => array
N => size of array
l => left edge
r => right edge
f => father pointer
s => son pointer

    //Heap Sort: sift() and heapsort()
    private static void sift(int[] a, int leftEdge, int rightEdge)
    {
        int fatherPointer = leftEdge;
        int sonPointer = 2 * leftEdge;
        int temp = a[fatherPointer];
        boolean found = false;
        
        while(!found && sonPointer <= rightEdge)
        {
            if(sonPointer < rightEdge && a[sonPointer-1] < a[sonPointer])
                sonPointer = sonPointer + 1;
            if(temp >= a[sonPointer-1])
                found = true;
            else
                a[fatherPointer-1] = a[sonPointer-1];
            fatherPointer = sonPointer;
            sonPointer = 2 * fatherPointer;
        }//while(!found && sonPointer <= rightEdge)
        
        a[fatherPointer-1] = temp;
    }//private static void sift(int[] a, int leftEdge, int rightEdge)

    public static void heapsort(int[] a, int n)
    {
        int leftEdge = n / 2 + 1;
        int rightEdge = n;
        int temp;
        
        while(leftEdge > 1)
        {
            leftEdge = leftEdge - 1;
            sift(a, leftEdge, rightEdge);
        }//while(leftEdge > 1)
        
        while(rightEdge > 1)
        {
            temp = a[0];
            a[0] = a[rightEdge - 1];
            a[rightEdge - 1] = temp;
            rightEdge = rightEdge - 1;
        }//while(rightEdge > 1)
    }//public static void heapsort(int[] a, int n)