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
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] = {
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 Basics.Comparison.
Changed by Russ Atkinson on July 26, 1983 12:38 pm
Formatted. Changed Basics to Basics.