-- File: HeapSort.mesa,  Last Edit: HGM  September 23, 1980  9:07 PM

DIRECTORY
  HeapSortDefs;

HeapSort: MONITOR EXPORTS HeapSortDefs =
  BEGIN

  -- Knuth vol 3 section 5.2.3 algorithm H  (pg 146)

  HeapSort: PUBLIC PROCEDURE [
    base: POINTER, length: CARDINAL,
    less: PROCEDURE [UNSPECIFIED, UNSPECIFIED] RETURNS [BOOLEAN]] =
    BEGIN
    array: POINTER TO ARRAY OF UNSPECIFIED ← base;
    i, j, l, r: CARDINAL;
    key: UNSPECIFIED;
    IF length <= 1 THEN RETURN;
    l ← length/2;
    r ← length - 1;
    DO
      IF l > 0 THEN BEGIN l ← l - 1; key ← array[l]; END
      ELSE
	BEGIN
	key ← array[r];
	array[r] ← array[0];
	r ← r - 1;
	IF r = 0 THEN BEGIN array[0] ← key; EXIT; END;
	END;
      j ← l;
      DO
	i ← j;
	j ← j*2 + 1;
	IF j > r THEN EXIT;
	IF j < r AND less[array[j], array[j + 1]] THEN j ← j + 1;
	IF ~less[key, array[j]] THEN EXIT;
	array[i] ← array[j];
	ENDLOOP;
      array[i] ← key;
      ENDLOOP;
    END;

  END.