-- 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.