<> <> <> <> DIRECTORY Basics 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 = Basics.Comparison; Sort: PUBLIC PROC [l: LIST OF Item] RETURNS [LIST OF Item] = { <> <> <> 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]; <> <<4 or NIL, lists[2] is a sorted list of length 8 or NIL, etc.>> <> x: CARDINAL; --[0..max] xMax: CARDINAL _ 0; --[0..max) <> <> 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; <> <> <> x _ 0; IF a = NIL THEN { <> UNTIL (lists[x] # NIL OR x = xMax) DO x _ x+1 ENDLOOP; a _ lists[x]; lists[x] _ NIL; x _ x+1 }; < xMax.>> UNTIL x > xMax DO IF (b _ lists[x]) # NIL THEN { lists[x] _ NIL; mergeTo _ mergeToCons; DO <> 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 <> Changed by MBrown on 23-Aug-81 18:01:01 <> Changed by MBrown on March 10, 1982 2:48 pm <> Changed by MBrown on June 28, 1982 10:24 am <> Changed by MBrown on August 26, 1982 6:16 pm <> Changed by Russ Atkinson on July 26, 1983 12:38 pm <>