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,d75494dd10472a30
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2002-03-01 16:03:49 PST
Path: 
 archiver1.google.com!news1.google.com!sn-xit-02!sn-post-02!sn-post-01!supernews.com!corp.supernews.com!not-for-mail
From: "Matthew Heaney" <mheaney@on2.com>
Newsgroups: comp.lang.ada
Subject: Re: Ada Components - GRACE Lists (Sorting them)
Date: Fri, 1 Mar 2002 19:09:11 -0500
Organization: Posted via Supernews, http://www.supernews.com
Message-ID: <u805n3q3m2e5e5@corp.supernews.com>
References: <a48p2k$nop$1@nh.pace.co.uk> <3C76EE71.40506@telepath.com>
 <a5fs6c$2cir$1@msunews.cl.msu.edu>
 <4519e058.0202260859.4ecde69f@posting.google.com>
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 6.00.2600.0000
X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2600.0000
X-Complaints-To: newsabuse@supernews.com
Xref: archiver1.google.com comp.lang.ada:20676
Date: 2002-03-01T19:09:11-05:00
List-Id: <comp.lang.ada>


"Ted Dennison" <dennison@telepath.com> wrote in message
news:4519e058.0202260859.4ecde69f@posting.google.com...
> When I do finally manage to find a suitable forum to publish the
> implmentation I have, we should certianly encourage folks to play with
> the algorithm, modify it, analayze the results, and report their
> findings for discussion. But again, I don't think we should waste a
> huge amount of effort on it, because this isn't the sort that will
> really matter. That one will be in the "Maps" package, and will
> probably have to be some kind of tree-based sort.

In the Charles data structure and algorithm library, I included a quicksort
to sort arrays (using the median-of-3 technique), and another to do a stable
sort of a list.  I haven't tried to do any other optimizations or anything.

http://home.earthlink.net/~matthewjheaney/charles/charles-generic_quicksort_
_ads.htm

http://home.earthlink.net/~matthewjheaney/charles/charles-unbounded_lists-ge
neric_quicksort__ads.htm

http://home.earthlink.net/~matthewjheaney/charles/

http://home.earthlink.net/~matthewjheaney/charles-20020228.zip

http://home.earthlink.net/~matthewjheaney/

Note that in Charles, the map and set types are implemented using a
red-black tree, so they're already sorted.