Time and Space Complexity

Time Complexity:

• Best, Average, and Worst Case: O(n log n)
  • Building the heap is O(n), and each of the n extractions costs O(log n) for the sift-down. There is no bad-input case that degrades it.

Space Complexity:

• O(1)
  • Heap Sort rearranges elements inside the original array and needs only a constant amount of extra memory.

Summary:

• Heap Sort combines a guaranteed O(n log n) running time with O(1) extra space, a combination Merge Sort and Quick Sort do not both offer.
• It is not stable (equal elements may change relative order), which is its main trade-off.