Analysis of heapsort

Schaffer R.W.

Heapsort is a classical sorting algorithm doe to Williams. Given an array to sort, Heapsort first transforms the keys of the array into a heap. The heap is then sorted by repeatedly swapping the root of the heap with the last key in the bottom row, and then sifting this new root down to an appropriate position to restore heap order. This thesis analyzes the asymptotic number of executions of each instruction for both versions of Heapsort in the average, best, and worst cases.