Heaps and Heap Sort

The following video explains heap sort, and compares it with merge sort.

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.

See also


A book about computers for ages 9+

NEW!
Demonstration of Compression

A physics riddle

Binary and Hexadecimal numbers