The heapsort time complexity is nlog(n) in all cases.
But I do not understand why because we must call n times the heapify algorithm ont the child binary trees with "i" which are already ilog(i) complexity.
The heapify operation takes O(lg(n))
time. When you swap the max/min node with another one from the bottom of your heap, you will have to push that node back to the bottom. Because there are n
elements and the height of the heap is equal lg(n)
, you will do lg(n)
swaps as your node traverses the heap down. If you repeat this n
times, the time will be O(nlg(n))
.
In the worst case (input sorted, but in reverse order) both building heap and sorting will be O(nlg(n))
. In the best case (sorted input) building will be O(n)
and sorting will be O(nlg(n))
(O(n)
if input consists of equal values). In average case building will be in between best and worst case, sorting will be O(nlg(n))
.