Heap Sort

Algorithm

proc heap-sort(A, n)
	for r = floor(n/2) downto 1 do sift(r, n)
	for m = n downto 2 do
		A[1] <-> 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

Creation comparisons

We consider the worst case for creating the heap.

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.