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]; 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 }; 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 ŔOnlineMergeSortImpl.mesa MBrown on August 26, 1982 6:16 pm Maxwell, January 6, 1983 12:15 pm Russ Atkinson, July 26, 1983 12:37 pm 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. 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). make each pair of consecutive elements of l into a sorted list of length 2, then merge it into lists. 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). try to make a # NIL. a # NIL OR x > xMax. a#NIL AND b#NIL By editing OnlineMergeSortRef. Fix bug in sorting NIL. 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. CEDAR implementation. Use Basics.Comparison. Formatted. Changed Basics to Basics. Ę˜šœ™Jšœ!™!Jšœ!™!J™%—J˜šĎk ˜ Jšœœ˜Jšœ œ˜)J˜—šœœ˜"Jšœ ˜Jšœ ˜Jšœ ˜Jšœ˜J˜Jšœœ˜J˜#Jšœ œ˜%J˜J˜—šĎnœœœœœœœœ ˜>JšœX™XJšœQ™QJšœ™Jšœœœ˜Jš œ œœœ œ˜0JšœœĎc.˜Bš œœ œœœœœ˜2JšœQ™QJšœ<™