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