-- File OnlineMergeSortImpl.mesa
-- Last edited by MBrown on August 26, 1982 6:16 pm
-- Last Edited by: Maxwell, January 6, 1983 12:15 pm


  DIRECTORY
    Environment USING [Comparison],
    ListSort USING [Item, nullItem, Compare];

OnlineMergeSortImpl: CEDAR PROGRAM
  IMPORTS
    ListSort
  EXPORTS
    ListSort
  SHARES
    ListSort
  = BEGIN

  Item: TYPE = ListSort.Item;
  nullItem: Item = ListSort.nullItem;
  Comparison: TYPE = Environment.Comparison;


  Sort: PUBLIC PROC [l: LIST OF Item] RETURNS [LIST OF Item] = {
    -- The sort is destructive and NOT stable, that is, the relative positions in the result of
    --nodes with equal keys is unpredictible.  For a nondestructive sort, copy l first.
    -- The sort does one CONS.
  a, b, mergeTo: LIST OF Item;
  mergeToCons: LIST OF Item = CONS[nullItem, NIL];
  max: CARDINAL = 22; --number of bits in word-address space minus 2
  lists: ARRAY [0..max) OF LIST OF Item ← ALL [NIL];
    -- lists[0] is a sorted list of length 2 or NIL, lists[1] is a sorted list of length
    --4 or NIL, lists[2] is a sorted list of length 8 or NIL, etc.
    -- When Sort returns, lists = ALL [NIL] again (we do some extra work to assure this).
  x: CARDINAL; --[0..max]
  xMax: CARDINAL ← 0; --[0..max)
  
  -- make each pair of consecutive elements of l into a sorted list of length 2,
  --then merge it into lists.
  UNTIL (a ← l) = NIL OR (b ← a.rest) = NIL DO
    l ← b.rest;
    IF ListSort.Compare[a, b] = less THEN {
      a.rest ← b; b.rest ← NIL }
    ELSE {
      b.rest ← a; a.rest ← NIL; a ← b };
    x ← 0;
    DO
      IF (b ← lists[x]) = NIL THEN {
        lists[x] ← a; EXIT }
      ELSE { --merge (equal length) lists a and b
        lists[x] ← NIL;
        mergeTo ← mergeToCons;
        DO --assert a#NIL, b#NIL
          IF ListSort.Compare[a, b] = less THEN {
            mergeTo.rest ← a;  mergeTo ← a;
            IF (a ← a.rest) = NIL THEN { mergeTo.rest ← b; EXIT } }
          ELSE {	
            mergeTo.rest ← b;  mergeTo ← b;
            IF (b ← b.rest) = NIL THEN { mergeTo.rest ← a; EXIT } }
          ENDLOOP;
        a ← mergeToCons.rest;
        x ← x+1;
        IF x > xMax AND (xMax ← x) = max THEN ERROR }
      ENDLOOP;
    ENDLOOP;
  -- xMax now contains the largest x such that lists[x] # NIL.
  -- if l's length was even, a = NIL; if l's length was odd, a = single element list.
  
  -- merge a and elements of lists into result (held in a).
  x ← 0;
  IF a = NIL THEN {
    -- try to make a # NIL.
    UNTIL (lists[x] # NIL OR x = xMax) DO x ← x+1 ENDLOOP;
    a ← lists[x];  lists[x] ← NIL;  x ← x+1 };
  -- a # NIL OR x > xMax.
  UNTIL x > xMax DO
    IF (b ← lists[x]) # NIL THEN {
      lists[x] ← NIL;
      mergeTo ← mergeToCons;
      DO
        -- a#NIL AND b#NIL
        IF ListSort.Compare[a, b] = less THEN {
          mergeTo.rest ← a;  mergeTo ← a;
          IF (a ← a.rest) = NIL THEN { mergeTo.rest ← b; EXIT } }
        ELSE {	
          mergeTo.rest ← b;  mergeTo ← b;
          IF (b ← b.rest) = NIL THEN { mergeTo.rest ← a; EXIT } }
        ENDLOOP;
      a ← mergeToCons.rest };
    x ← x+1;
    ENDLOOP;
  RETURN [a]
  };--Sort



END.--OnlineMergeSortImpl


CHANGE LOG

Created by MBrown on 19-Aug-81 16:14:56
-- By editing OnlineMergeSortRef.

Changed by MBrown on 23-Aug-81 18:01:01
-- Fix bug in sorting NIL.

Changed by MBrown on March 10, 1982 2:48 pm
-- Use a bounded array in local frame instead of consing up a list of lists on each call.
--Even for a 32 bit address space, this is only 60 words of array in the frame.

Changed by MBrown on June 28, 1982 10:24 am
-- CEDAR implementation.

Changed by MBrown on August 26, 1982 6:16 pm
-- Use Environment.Comparison.