Bottom-Up-Heapsort

BottomUp-Heapsort ist ein Sortieralgorithmus, der u. a. 1990 von Ingo Wegener vorgestellt wurde und im Durchschnitt besser als Quicksort arbeitet, falls man Vergleichsoperationen hinreichend stark gewichtet. Es ist eine Variante von Heapsort, die vor allem zur Sortierung sehr großer Datenmengen geeignet ist, wenn (im Vergleich zu den notwendigen Vertauschungsoperationen) ein relativ hoher Aufwand pro Vergleichsoperation erforderlich ist.

Diese Variante wurde allerdings bereits 1986 von Svante Carlsson analysiert, der letztlich eine weitere Variante fand, die sogar eine worst-case-Laufzeit von nur n log n + O(n log log n) Vergleichen hat. Entdeckt wurde dieser Bottom-Up-Heapsort bereits von Robert W Floyd (bei einer Überarbeitung des ursprünglichen Heapsorts von Williams), der aber das Laufzeitverhalten dieser Variante nicht beweisen konnte.

Er benötigt zum Sortieren einer Folge von n Schlüsseln im schlechtesten Fall nur 1,5 n log n + 2n Schlüsselvergleiche. Im Durchschnittsfall benötigt BottomUp-Heapsort nur n log n + O(n) Schlüsselvergleiche.