Heapsort

“Like merge sort, but unlike insertion sort, heapsort’s running time is O(n*lg(n)). Like insertion sort, but unlike merge sort, heapsort sorts in place: only a constant number of array elements are stored outside the input array at any time. Thus, heapsort combines the better attribute of the two sorting algorithms …” [Introduction to Algorithms]

void heapSort(int *a)
{
    for(int i = arraySize; i > 1; --i)
    {
        for(int k = 0; k < i; ++k)
        {
            // compare each element with its parent
            // if the child is begger than its parent
            // then swap them
            // keep doing this until reaching the root
            while((a[k] > a[k/2]) && (k > 0))
            { 
                swap(a[k], a[k/2]); 
                k = k/2; 
            }
        }
        // After the for loop, the largest is put at a[0]
        // then put the largest to the end of the array
        // and find the largest of the rest in the same way
        swap(a[0], a[i-1]);
    }
}