Heapsort

• $O(n\lg n)$, but sorts in place, so that the memory usage is constant.
• Utilizes the heap data structure.

heapsort(A, n)
    for i = n downto 2
        exchange(A[1], A[i])
        A.heap_size -= 1
        max_heapify(A, 1)