Heapsort Analysis
Now that we've seen how heapsort operates, let's think about how efficient it is.
Time analysis
We saw in the previous lesson that heapsort consists of two main steps:
- Convert an arbitrary list into a heap.
- Repeatedly remove the maximum element from a heap until you get a sorted list.
As we saw in the heap construction lesson, step (1) above takes time O(n). After this step is done, we then repeatedly remove the maximum element. In fact we remove n - 1 = O(n) such elements, and each call to remove() takes time O(logn) in order to put the heap back into order. Therefore, the running time of the second step is O(n) * O(logn) = O(nlogn).
Putting the two steps together, we get O(n) + O(nlogn) = O(nlogn). This is just as efficient as mergesort!
Space analysis
Although heapsort has the same running time as mergesort, it actually performs better in terms of space. Whereas mergesort requires an auxiliary list to be able to work (which means O(n) extra space), the heapsort algorithm can be performed in-place, using only a constant amount of extra space for local variables. Notice that in the visualizations of heapsort shown in the previous lesson, all the work is done in the same list that was passed in!
Completing our table of sorting algorithm analysis, we can now add heapsort:
| Algorithm | Best case | Worst case | Space |
|---|---|---|---|
| Selection sort | O(n2) | O(n2) | O(1) |
| Insertion sort | O(n) | O(n2) | O(1) |
| Mergesort | O(nlogn) | O(nlogn) | O(n) |
| Radix sort | O(m*n) | O(m*n) | O(n) |
| Heapsort | O(nlogn) | O(nlogn) | O(1) |