Heapsort

heapsort (int a[ ], int N) /*sortiert a[1] bis a[N] */

{

int k, t; /*wandle a[1] bis a[N] in Heap um*/

for (k=N/2; k>=1; k- -) downheap (a, N, k);

while (Nɭ)

{

/*vertausche a[1] und a[N] und laß a[1] versickern*/

t= a[1]; a[1]= a[N]; a[N] = t;

downheap (a, - -N, 1);

}

Worst case Komplexität:

Aufruf von downheap erzeugt höchstens log N Vertauschungen.

N/2 + N-1 mal aufgerufen, damit also O(N log N).

Zusätzlicher Speicherplatz konstant, also echtes in situ (in place) Verfahren.