# 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.

• The $\frac{n}{2}$ leaves do $0$ comparisons.
• The $\frac{n}{4}$ parents do $2$ comparisons.
• The $\frac{n}{8}$ grandparents do $4$ comparisons.
• $\dots$

We can find a closed form of this sum with some clever algebra.

• $0\left(\frac{n}{2}\right)+2\left(\frac{n}{4}\right)+4\left(\frac{n}{8}\right)+\dots$
• $=\left(\frac{n}{2}\right)\left(\frac{1}{1}+\frac{2}{2}+\frac{3}{4}+\frac{4}{8}+\dots \right)$
• $=\left(\frac{n}{2}\right)\left($
• $1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots =2$
• $\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\dots =1$
• $\frac{1}{4}+\frac{1}{8}+\dots =\frac{1}{2}$
• $\frac{1}{8}+\dots =\frac{1}{4}$
• $\dots \right)=\left(\frac{n}{2}\right)\left(4\right)$
• $=2n$

## 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.

• $\underset{i=0}{\overset{n-1}{\Sigma }}2lg\left(n-1\right)$
• $=2nlgn+O\left(n\right)$