Heapsort Aufwand

Theta(n log(n)) ist richtig. Das ist auch die Komplexität des Sortierproblems, der Algorithmus kann daher gar nicht schneller sein (und auch kein anderer).

Zitat von Christoph R.

Theta(n log(n)) ist richtig. Das ist auch die Komplexität des Sortierproblems, der Algorithmus kann daher gar nicht schneller sein (und auch kein anderer).

dem stimme ich (bzw mein algodat-skript) zu. vielleicht zusaetzlich noch interessant:
C_max = C_avg = C_min = Theta (n log (n))
M_max = M_avg = M_min = Theta (n log (n))