TYPE index = INTEGER; item = INTEGER;
VAR a: ARRAY [-9..8192] OF item;
PROCEDURE HeapSort (n:
CARDINAL);
VAR L, R: index; x: item;
PROCEDURE sift(L, R: index);
VAR i, j: INTEGER; x: item;
BEGIN i := L; j := 2*L; x := a[L];
IF (j < R) & (a[j] < a[j+1]) THEN j := j+1 END;
WHILE (j <= R) & (x < a[j])
DO
a[i] := a[j]; i := j; j := 2*j;
IF (j < R) & (a[j] < a[j+1]) THEN j := j+1 END
END
END sift;
BEGIN L := (n
DIV 2) + 1; R := n;
WHILE L > 1 DO L := L-1; sift(L, R) END;
WHILE R > 1
DO
x := a[1]; a[1] := a[R]; a[R] := x;
R := R-1; sift(L, R)
END
END HeapSort;
PROCEDURE QuickSort (n: CARDINAL);
PROCEDURE sort (L, R: index);
VAR i, j: index; w, x: item;
BEGIN i := L; j := R;
x := a[(L+R) DIV 2];
REPEAT
WHILE a[i] < x DO i := i+1 END;
WHILE x < a[j] DO j := j-1 END;
IF i <= j
THEN
w := a[i]; a[i] := a[j]; a[j] := w; i := i+1; j := j-1
END
UNTIL i > j;
IF L < j THEN sort(L, j) END;
IF i < R THEN sort(i, R) END
END sort;
BEGIN sort(1, n)
END QuickSort;