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-11 01:37:57 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!isdnet!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> From: Jean-Marc Bourguet Date: 11 Jan 2002 10:37:52 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Message-ID: <3c3eb272$0$282$626a54ce@news.free.fr> Organization: Guest of ProXad - France NNTP-Posting-Date: 11 Jan 2002 10:37:56 MET NNTP-Posting-Host: 158.140.208.29 X-Trace: 1010741876 news1-1.free.fr 282 158.140.208.29 X-Complaints-To: abuse@proxad.net Xref: archiver1.google.com comp.lang.ada:18764 Date: 2002-01-11T10:37:56+01:00 List-Id: dennison@telepath.com (Ted Dennison) writes: > Jean-Marc Bourguet wrote in message news:<3c3bfabc$0$3190$626a54ce@news.free.fr>... > > Ted Dennison writes: > > > > > That's a good point. It would probably be fairly easy to alternate > > > which side the pivot is taken from. > > > > This will not change the behaviour in N^2 for a (nearly) sorted input. > > After thinking about it harder, you are right. Everything will allways > go on one side of the pivot, no matter which side you take it from. So > no "dividing" will actually happen, which is where this > divide-and-conquer algorithm gets its speed from. > > > > I believe the splitting part of mergesort would involve a linear > > > search for a linked-list. That would take us into O(n*2) territory, > > > if not worse. In my student days I could figure out the exact > > > factor...hmmm...perhaps its just another nlogn... > > > > Merge sort can be implemented in O(N log N) worst case, with a O(N) > > for an already sorted input. > > OK. By arguing through repeated assertion, you are forcing to either > ignore you, or do the work of proof myself. Since I made the first > claim, its only fair that I do the work I guess... I think the proof is in The Art Of Computer Programming (Knuth, volume three). > ...OK it looks like the work involved in doing *all* the splits using > linear searches is (n/2 + 2(n/4) + 4(n/8) ....) where n>1. Since there > is one of these factors for each "level", and there are logn levels, > that should work out to roughly (n/2)logn, or O(n logn). So you are > right that it is O(N log N) worst case. However, you are wrong about > the best case. With a linked-list, that is *also* O(N log N). Not tested, not even compiled, but it should show the principles. I think it is in the section "external sorting" of Knuth. I think the sort is stable which is an added bonus (but this should be verified). type Node; type Node_Ptr is access Node; type Node is record Next: Node_Ptr; Value: Value_Type; end record; procedure Sort (Head : in out Node_Ptr) is procedure Append(N : Node_Ptr; Last, Other: in out Node_Ptr; L1, L2: out Node_Ptr) is begin if Last = null then Last := N; L1 := N; else if Last.Value <= N.Value then Last.Next := N; Last := N; else if Other = null then Other := Last; Last := N; L2 := N; else declare Tmp : Node_Ptr := Last; begin Last := Other; Other := Tmp; Last.Next := N; Last := N; end; end if; end Append; procedure Split(Head: Node_Ptr; L1, L2: out Node_Ptr) is Current : Node_Ptr := Head; Last : Node_Ptr := Null; Other : Node_Ptr := Null; begin -- Split L1 := null L2 := null; while Current /= null loop declare Next : Node_Ptr := Current.Next; begin Append(Current, Last, Other, L1, L2); Current := Next; end; end loop; Last.Next := null; if Other /= null then Other.Next := null end if; end Split; procedure Merge(L1, L2: in out Node_Ptr) is Current1 : Node_Ptr := L1; Current2 : Node_Ptr := L2; Last : Node_Ptr := null; Other : Node_Ptr := Null; Tmp : Node_Ptr := Null; begin -- Merge L1 := null; L2 := null; while Current1 /= null and Current2 /= null loop if Current1.Value <= Current2.Value then declare Next : Node_Ptr := Current1.Next; begin Append(Current1, Last, Other, L1, L2); Current1 := Next; end; else declare Next : Node_Ptr := Current2.Next; begin Append(Current2, Last, Other, L1, L2); Current2 := Next; end; end if; end loop; if Current1 /= null then Tmp := Current1; else Tmp := Current2; end if; while Tmp /= null loop declare Next : Node_Ptr := Tmp.Next; begin Append(Tmp, Last, Other, L1, L2); Tmp := Next; end; end loop; Last.Next := null; if Other /= null then Other.Next := null end if; end Merge; begin -- Sort if Head = Null then return; end if; Split(Head, L1, L2); while L2 /= Null loop Merge(L1, L2); end loop; Head = L1; end Sort; Each split and Merge phase are O(n). If the list is sorted, only Split is done. Merge reduce the number of chunks by a factor 2 and there is at most N chunks (if the list is in the reverse order), so worse case is O(N log N). -- Jean-Marc