Time and Space Complexity

Zeitkomplexität:

• Best-, Durchschnitts- und Worst-Case: O(n log n)
  • Das Erstellen des Heaps ist O(n), und jede der n Extraktionen kostet O(log n) für das Sift-Down. Es gibt keinen Fall mit schlechten Eingabedaten, der die Performance verschlechtert.

Platzkomplexität:

• O(1)
  • Heap Sort ordnet Elemente innerhalb des ursprünglichen Arrays um und benötigt nur eine konstante Menge an zusätzlichem Speicher.

Zusammenfassung:

• Heap Sort kombiniert eine garantierte Laufzeit von O(n log n) mit O(1) zusätzlichem Speicherplatz, eine Kombination, die Merge Sort und Quick Sort nicht beide bieten.
• Es ist nicht stabil (gleiche Elemente können ihre relative Reihenfolge ändern), was sein Hauptnachteil ist.