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=0.6 required=5.0 tests=BAYES_00,TO_NO_BRKTS_FROM_MSSP autolearn=no 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-08 14:13:19 PST Path: archiver1.google.com!news1.google.com!sn-xit-02!supernews.com!newsfeed.direct.ca!look.ca!news.maxwell.syr.edu!out.nntp.be!propagator-SanJose!in.nntp.be!newsranger.com!www.newsranger.com!not-for-mail Newsgroups: comp.lang.ada From: Ted Dennison References: <7iE_7.8661$cD4.15714@www.newsranger.com> Subject: Re: list strawman Message-ID: X-Abuse-Info: When contacting newsranger.com regarding abuse please X-Abuse-Info: forward the entire news article including headers or X-Abuse-Info: else we will not be able to process your request X-Complaints-To: abuse@newsranger.com NNTP-Posting-Date: Tue, 08 Jan 2002 17:13:10 EST Organization: http://www.newsranger.com Date: Tue, 08 Jan 2002 22:13:10 GMT Xref: archiver1.google.com comp.lang.ada:18671 Date: 2002-01-08T22:13:10+00:00 List-Id: In article , Georg Bauhaus says... > >Another suggestion: Saving the current length of the list will allow >a quick inspection to choose an algorithm, so Insertion Sort could be >used for short lists, which can be made stable and is faster for doubly >linked lists than for arrays. >Also, it does not have the n**2 problem for pre-sorted lists. We probably don't want to get into the business of specifying implementations. It may be reasonable to say things like "sort should be O(nlogn) in the average case.", or "sort shall be stable", or even "Size should be O(C) in the worst case". But I think what sort algorithm to use should be almost entirely left up to the discretion of the implementors. Now you might have meant this as a suggestion to us implementors. For my reference implementation, I'm planning on just using a relatively simple Quicksort (hopefully in-place, non-recursive, and stable). I don't care that much about efficiency for small lists because the Sort is going to be quick on small lists anyway, so there isn't all that much time to gain. Its not really worth undully complicating things for them. I also don't really think its worth pouring mass quantities of effort into making this sort as fast as possible, since "*.Maps.Unbounded.Map" will presumably be the place to turn when you want to deal with a sorted structure. --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html No trees were killed in the sending of this message. However a large number of electrons were terribly inconvenienced.