# Why is the running time of heapsort $O(n\log n)$?

Heapsort(A)
1 BUILD_MAX_HEAP(A)
2 for i=A.length downto 2
3    exchange A[1] with A[i]
4    A.heapsize=A.heapsize-1
5    MAX_HEAPIFY(A,1)


In the book on algorithms by CLRS the running time of this algorithm is given to be $O(n\lg n)$ as the for loop is executed $n-1$ times and each call of MAX_HEAPIFY takes $O(\lg n)$.

But my question is does MAX_HEAPIFY not depend on height of subtree at which it is called? Why then should it still be the same for all $n-1$ calls as $h$ will obviously differ?

• Duplicate? Sep 18, 2015 at 17:53

Each call of MAX_HEAPIFY takes time $O(h) = O(\log n)$, where $h$ is the depth of the heap. Note that big O is an upper bound on the running time, not the exact running time. It is also true that the running time of MAX_HEAPIFY is $O(n)$, for example.
The underlying datasctructure of heapsort is -like the name suggests- a heap. A heap has the property, that it is always complete except for the lowest level of the tree. That means, if you have $n$ Nodes, the maximum height of the tree is $logn$. Since heaps are usually implemented as Arrays you can easily compare parent and child nodes (e.g. let i be an index in the array, then the left child of any given node has the index $2i$, the right child has the index $2i+1$) and therefor you dont need to worry about any other complexity then the $logn$ element-comparisions and potential swaps you have to do, when running MAX_HEAPIFY.
The height indeed varies, so that the total count is $n$ times the average height.