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-09 00:09:34 PST Path: archiver1.google.com!news1.google.com!newsfeed.stanford.edu!bloom-beacon.mit.edu!news-out.cwix.com!newsfeed.cwix.com!opentransit.net!wanadoo.fr!proxad.net!feeder2-1.proxad.net!news2-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> From: Jean-Marc Bourguet Date: 09 Jan 2002 09:09:31 +0100 MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Message-ID: <3c3bfabc$0$3190$626a54ce@news.free.fr> Organization: Guest of ProXad - France NNTP-Posting-Date: 09 Jan 2002 09:09:33 MET NNTP-Posting-Host: 158.140.208.29 X-Trace: 1010563773 news2-1.free.fr 3190 158.140.208.29 X-Complaints-To: abuse@proxad.net Xref: archiver1.google.com comp.lang.ada:18678 Date: 2002-01-09T09:09:33+01:00 List-Id: Ted Dennison writes: > In article <3c3b2aa0$0$212$626a54ce@news.free.fr>, Jean-Marc Bourguet says... [...] > >Yes. There is still the problem of choosing the pivot. With > >random access, I'd use a random element. Without random access, > >you'll have to choose the first or the last element and then > >degenerate in N^2 for a sorted input, not something I'd like in a > >general purpose library. > > 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. [...] > 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. > Despite taking Computer Science Algorithms courses no less than 3 > times (or perhaps *because* I had to :-) ), I'm not really a sorting > expert. But all the literature I read highly suggests one use > Quicksort, despite its theoretical O(n**2) > behavior. http://www.cs.ubc.ca/spider/harrison/Java/sorting-demo.html > is a good example. Most litterature I've read is about sorting arrays. AFAIK, it is not possible to do merge sort in place for arrays (but it is for linked list, even singly linked list) and that's probably why this algorithm is often neglected. Yours, -- Jean-Marc