MODULE Sort; (*JG, 1.9.85*)

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;

BEGIN HeapSort (100); QuickSort (100)
END Sort.