Heap Sort erstellt einen binären Heap aus dem Array und extrahiert dann wiederholt das Maximum, um sortierte Reihenfolge zu erzeugen. Es läuft in O(n log n) und ist in-place.
Die Idee
Ein Max-Heap behält das größte Element an der Wurzel. Erstellen Sie den Heap (O(n)), tauschen Sie dann die Wurzel ans Ende, verkleinern Sie den Heap und führen Sie ein erneutes Heapify (sift down) durch — n-mal.
