Today we'll finish heapsort, and describe both mergesort and quicksort.
Different methods work better in different applications.
Heapsort uses close to the right number of comparisons but needs to move data around quite a bit. It can be done in a way that uses very little extra memory. It's probably good when memory is tight, and you are sorting many small items that come stored in an array. Merge sort is good for data that's too big to have in memory at once, because its pattern of storage access is very regular. It also uses even fewer comparisons than heapsort, and is especially suited for data stored as linked lists.