Heap Sort

Internal

• Algorithms
• Sorting Algorithms
• Heaps

Overview

Worst-case time	O(n lgn)
Average-case time
Best-case time

Algorithm

For each element we need to sort, insert it in a min heap, using the heap's INSERT operation. The running time of an individual INSERT is O(log n), so the insertion in a loop will have a running time of O(n log n). Once all the elements that need to be sorted are placed in the min heap, extract the minimum element from the heap, also in a loop, with REMOVE-MIN and place it in order in the final array. The running time of the second phase is O(n log n). The total running time is O(n log n).