# Proof of the average case of the Heap Sort algorithm

Consider the following python implementation of the Heap Sort algorithm:

def heapsort(lst):
length = len(lst) - 1
leastParent = length // 2
for i in range (leastParent, -1, -1):
moveDown(lst, i, length)

for i in range(length, 0, -1):
if lst[0] > lst[i]:
swap(lst, 0, i)
moveDown(lst, 0, i - 1)

def moveDown(lst, first, last):
largest = 2 * first + 1
while largest <= last:
# right child is larger than left
if (largest < last) and (lst[largest] < lst[largest + 1]):
largest += 1

# right child is larger than parent
if lst[largest] > lst[first]:
swap(lst, largest, first)
# move down to largest child
first = largest;
largest = 2 * first + 1
else:
return # exit

def swap(lst, i, j):
tmp = lst[i]
lst[i] = lst[j]
lst[j] = tmp


I have been able to formally prove that worst-case is in $$\Theta(n \log(n))$$ and that the best-case is in $$\Theta(n)$$ (some might argue the best-case is in $$\Theta(n \log(n))$$ as well since that's what most searches on the internet will return but just think of what happens when an input list where all of the elements are the same number).

I have showed both upper and lower bounds of the worst and best-case by realizing that the route taken by moveDown function is dependent on the height of the heap/tree and whether the elements in the list are distinct or the same number across the whole list.

I have not been able to prove the average case of this algorithm which I know is also in $$\Theta(n \log(n))$$. I do know, however, that I am supposed to consider an input set or family of lists of all length $$n$$ and I am allowed to make an assumption such as that all of the elements in the list are distinct. I confess that I am not good at average-case analysis and would really appreciate it if someone could give a complete and thorough proof(including the exact expressions especially of the number of inputs) as it would help me understand the concept a great deal.

• If best and worst cases are $\Theta(n \log n)$, all cases fall in between and their average does too. – vonbrand Aug 12 at 13:59