Jyrki Katajainen stellte 1996 das neue Sortierverfahren Ultimate Heapsort vor, das im worst case $n\log_{2}n + O(n)$ Vergleiche für das Sortieren von $n$ Schlüsseln benötigt. Damit ist die Lücke zwischen unterer Schranke von $\log_{2}(n!)$ Vergleichen und worst case zumindest theoretisch geschlossen. Volker Diekert verbessert Katajainens Ansatz und kann den viel zu hohen positiven Faktor des linearen Terms auf $18$ senken, was im Vergleich zu Bottom--Up--Heapsort für die Praxis immer noch uninteressant ist.

Es zeigt sich, daß eine große Anzahl von Vergleichen für die Lösung des Auswahlproblems verantwortlich für die Höhe des Faktors verantwortlich ist. Daher beschäftigt sich ein Abschnitt dieser Arbeit eingehend mit dem Auswahlproblem und stellt unter anderem ein Verfahren vor, welches das Auswahlproblem im \textit{average case} mit $3/2 \cdot n + o(n)$ Vergleichen lösen kann.

Beide Varianten von Ultimate Heapsort werden mit unterschiedlichen Auswahlverfahren zusammen getestet und empirische Ergebnisse ermittelt. Dabei stellt sich heraus, daß der Faktor im Durchschnitt nicht geringer als $7$ wird. Verglichen mit dem average case des Bottom--Up--Heapsort ist dieser Wert so hoch, daß Ultimate Heapsort für die Praxis uninteressant ist.

Dennoch besteht weiterhin ein theoretisches Interesse an Ultimate Heapsort: Das belegen die Untersuchungen von Laurent Rosaz, der nach eigenen Angaben den linearen Faktor im worst case auf $8$ senken konnte.