Der Algorithmus verwendet n-1 „siftup“- und „siftdown“ - Operationen,
von denen jede die Kosten O(log n) hat.
So kann auch im schlimmsten Fall O(n log n) garantiert werden.
Natürlich gibt es auch für Heapsort
Möglichkeiten den Algorithmus schneller und einfacher zumachen
(1.8 Verbesserte Implementation).
Obwohl Heapsort O(n log n) als worst-case Laufzeit hat, ist es immer
noch langsamer als Quicksort, das als worst-case Laufzeit nur O(n²)
aufweist.
Dies liegt natürlich daran , dass man bei Quicksort den
worst-case Fall durch geschickte Implementation verhindern kann
(siehe Vortrag Sorting).