From mboxrd@z Thu Jan 1 00:00:00 1970 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me X-Spam-Level: X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00 autolearn=ham autolearn_force=no version=3.4.4 X-Google-Language: ENGLISH,ASCII-7-bit X-Google-Thread: 103376,cda33fc7f63c2885 X-Google-Attributes: gid103376,public X-Google-ArrivalTime: 2002-01-13 02:23:46 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news-spur1.maxwell.syr.edu!news.maxwell.syr.edu!newsfeed00.sul.t-online.de!t-online.de!fr.usenet-edu.net!usenet-edu.net!proxad.net!feeder2-1.proxad.net!news1-1.free.fr!not-for-mail Newsgroups: comp.lang.ada Subject: Re: list strawman References: <7iE_7.8661$cD4.15714@www.newsranger.com> <3c3b13ba$0$212$626a54ce@news.free.fr> <3c3b2aa0$0$212$626a54ce@news.free.fr> <3c3bfabc$0$3190$626a54ce@news.free.fr> <4519e058.0201091037.325fbdbb@posting.google.com> <3c3eb272$0$282$626a54ce@news.free.fr> <3C3F1A0F.2000706@telepath.com> <7uir1a.s11.ln@192.168.0.2> From: Jean-Marc Bourguet Date: 13 Jan 2002 11:18:35 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Message-ID: Organization: Guest of ProXad - France NNTP-Posting-Date: 13 Jan 2002 11:23:45 MET NNTP-Posting-Host: 62.147.78.223 X-Trace: 1010917425 news1-1.free.fr 290 62.147.78.223 X-Complaints-To: abuse@proxad.net Xref: archiver1.google.com comp.lang.ada:18851 Date: 2002-01-13T11:23:45+01:00 List-Id: Jean-Marc Bourguet writes: > There is a sligth difference with was is presented in Knuth. He use an > additionnal flag in the record to mark the end of the sublists. I > didn't do that and used the fact that a sublist end when there is a > drop in value. This has a consequence that sublists may be merged > inexpectedly and so some care must be taken not to go in O(N^2). Here is a variant. Instead of detecting chunks by a drop in value, I mark the end of chunk with Null and keep the already constructed chunks in an array. To keep their number low, I merge them as they are constructed. Pure algorithm L is having procedure Extract_Next_Chunk (Head : in out Node_Ptr; Chunk : out Node_Ptr; Slot : out Table_Index) is Slot := 1; Chunk := Head; Head := Chunk.Next; Chunk.Next := null; end Extract_Next_Chunk; instead of what is below. -- Jean-Marc --------------------------------------------------------------------------- -- Natural List Merge Sort -- See D.E. Knuth, The Art Of Computer Programming, Volume 3, Second Edition -- Algorithm L section 5.2.4 modified according exercise 12 in the same -- section, modified to merge chunks as they are constructed instead of keeping -- them. Already constructed chunks are kept in an array. They are at most -- log_2(N). Big existing chunk are put at their place in the array, this help -- in the presence of nearly sorted input. procedure Sort (Head : in out Node_Ptr); -- Sort the linked list Head. procedure Sort (Head : in out Node_Ptr) is type Table_Index is range 1 .. 64; procedure Extract_Next_Chunk (Head : in out Node_Ptr; Chunk : out Node_Ptr; Slot : out Table_Index) is Last : Node_Ptr := Head; Current : Node_Ptr := Last.Next; Size : Integer := 1; Next : Integer := 2; begin -- Extract_Next_Chunk Chunk := Head; Slot := 1; while Current /= null loop pragma Assert (Current = Last.Next); if not Ordered (Last.Value, Current.Value) then Last.Next := null; Head := Current; return; end if; Last := Current; Current := Last.Next; Size := Size + 1; if Size = Next then Next := 2*Next; Slot := Slot + 1; end if; end loop; Head := null; pragma Assert (Last.Next = null); end Extract_Next_Chunk; function Merge (L1, L2 : Node_Ptr) return Node_Ptr is Current1 : Node_Ptr := L1; Current2 : Node_Ptr := L2; Last : Node_Ptr := null; Result : Node_Ptr := null; begin while Current1 /= null and Current2 /= null loop if Ordered (Current1.Value, Current2.Value) then if Last /= null then Last.Next := Current1; else Result := Current1; end if; Last := Current1; Current1 := Current1.Next; else if Last /= null then Last.Next := Current2; else Result := Current2; end if; Last := Current2; Current2 := Current2.Next; end if; end loop; if Current1 /= null then if Last /= null then Last.Next := Current1; else Result := Current1; end if; elsif Current2 /= null then if Last /= null then Last.Next := Current2; else Result := Current2; end if; end if; return Result; end Merge; type Node_Ptr_Table is array(Table_Index) of Node_Ptr; Chunk_Table : Node_Ptr_Table := (others => null); -- list pointed by chunk_table(i) as at least 2^(i-1) elements procedure Merge_With_Other_Chunks (Chunk : Node_Ptr; Slot : Table_Index) is Current : Node_Ptr := Chunk; I : Table_Index := Slot; begin -- Merge_With_Other_Chunks while Chunk_Table(I) /= null loop Current := Merge (Current, Chunk_Table(I)); Chunk_Table(I) := null; I := I+1; end loop; Chunk_Table(I) := Current; end Merge_With_Other_Chunks; Aux : Node_Ptr; Slot : Table_Index; begin -- Sort if Head = null then return; end if; while Head /= null loop Extract_Next_Chunk (Head, Aux, Slot); Merge_With_Other_Chunks (Aux, Slot); end loop; for I in Table_Index loop Head := Merge (Head, Chunk_Table(I)); end loop; end Sort;