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 09:03:56 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!newsfeed.direct.ca!look.ca!newshub2.rdc1.sfba.home.com!news.home.com!news1.elcjn1.sdca.home.com.POSTED!not-for-mail Message-ID: <3C3F1A0F.2000706@telepath.com> From: Ted Dennison User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.0; en-US; rv:0.9.7) Gecko/20011221 X-Accept-Language: en-us MIME-Version: 1.0 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> Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Date: Fri, 11 Jan 2002 17:03:54 GMT NNTP-Posting-Host: 24.10.28.160 X-Complaints-To: abuse@home.net X-Trace: news1.elcjn1.sdca.home.com 1010768634 24.10.28.160 (Fri, 11 Jan 2002 09:03:54 PST) NNTP-Posting-Date: Fri, 11 Jan 2002 09:03:54 PST Organization: Excite@Home - The Leader in Broadband http://home.com/faster Xref: archiver1.google.com comp.lang.ada:18780 Date: 2002-01-11T17:03:54+00:00 List-Id: Jean-Marc Bourguet wrote: > dennison@telepath.com (Ted Dennison) writes: > > >>...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). > 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; > Each split and Merge phase are O(n). If the list is sorted, only That's right, each call to those routines is O(n). However, for a mergesort you don't do just one split or merge. At the top level you do 1, and the next level you do 2, at the next 4, and so on. It doesn't look like the algorithm you presented does this, but then it doesn't look like a sort either. It only calls split once, and then merge. Its actually a O(n) algorithm. Too bad it doesn't actually sort, or you'd be up for some kind of prize. :-) Now lets assume it *did* sort, by having split call itself recursively after the split if there are multiple elements, then perform a merge when its done. The way this modified Split algorithm works, you essentially do one full linear search through every list element at every recusion level that the list has. Since you divide the list in half at each level, there are log N division levels. Thus this algorithm you presented is O(n log n), best, worst and average case, just like I was saying. The algorithm I assumed for my previous mergesort split calculations was a bit quicker, in that I only searched through *half* the list at each level, but the time behavior is the same.