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