So is Heap Sort really so bad?
Heap Sort has advantages and disadvantages when compared with any other top-notch algorithm.
Vs. Merge Sort
- Heap sort makes more comparisons than merge sort. This is why it loses the competition in the video.
- Heap sort uses less memory. As shown in the video, merge sort uses the entire upper shelf, whereas heap sort sorts in place on the lower shelf. In some circumstances this can result in significant speedup as well.
Vs. Quick Sort
- On average, quick sort is about as fast as merge sort, and much faster than heap sort.
- If we measure not the average performance, but the worst case performance, that is, the worst possible time it would take the algorithm to finish, then heap sort is far better than quick sort.
Conclusion
If you have very scarce time and memory resources, and the sorting algorithm must sort in-place, and not exceed some tight time limit, then heap sort is your algorithm of choice.