Złożoność czasowa i pamięciowa

Złożoność czasowa:

• Najlepszy, średni i najgorszy przypadek: O(n log n)
  • Budowa kopca ma złożoność O(n), a każde z n wyjęć kosztuje O(log n) ze względu na przesiewanie w dół. Nie ma przypadku złych danych wejściowych, który powodowałby pogorszenie wydajności.

Złożoność pamięciowa:

• O(1)
  • Heap Sort przestawia elementy w oryginalnej tablicy i wymaga jedynie stałej ilości dodatkowej pamięci.

Podsumowanie:

• Heap Sort łączy gwarantowany czas działania O(n log n) z dodatkową pamięcią O(1) — takiego połączenia nie oferują jednocześnie Merge Sort i Quick Sort.
• Nie jest stabilny (elementy o równych wartościach mogą zmienić kolejność względem siebie), co stanowi jego główny kompromis.