proc heap-sort(A, n) for r = floor(n/2) downto 1 do sift(r, n) for m = n downto 2 do A <-> A[m] sift(1, m-1)
proc sift(p, m) c = 2*p while c <= m if c < m then if A[c+1] > A[c] then c = c + 1 if A[c] > A[p] then A[p] <-> A[c] p = c c = 2*p else exit
We consider the worst case for creating the heap.
- The leaves do comparisons.
- The parents do comparisons.
- The grandparents do comparisons.
We can find a closed form of this sum with some clever algebra.
Heap sort comparisons
We consider the worst case for heap sort. We require two comparisons for every mini-heap. Sifts are proportional to the levels below the current node.