Heap Sort - rFronteddu/general_wiki GitHub Wiki

O(n log n)

1. buildMaxHeap, max will then be in A[1], exchange it to A[n]
2. We can remove n by decreasing size by 1
3. Heapify and exchange root
4. repeat

heapSort(A) {
    buildMaxHeap(A);
    for i = A.len to 2:
        swap (A, i, 1)
        A.size--;
        maxHeapify(A, 1)
}