Complexity of HeapSort

Heap sort has the time complexity of O(N log N) for all cases.

Note that heap sort is not stable. Stable sorting allows us to sort based on more than one key. Operations in the heap can change the relative order of equivalent keys-- picture the event of two identical numbers in the heap, which make their way to different locations.