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,FREEMAIL_FROM
	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-02-26 03:55:07 PST
Path: 
 archiver1.google.com!news1.google.com!newsfeed.stanford.edu!news.ems.psu.edu!news.cse.psu.edu!elk.ncren.net!nntp.upenn.edu!msunews!not-for-mail
From: "Chad R. Meiners" <crmeiners@hotmail.com>
Newsgroups: comp.lang.ada
Subject: Re: Ada Components - GRACE Lists (Sorting them)
Date: Tue, 26 Feb 2002 06:52:36 -0500
Organization: Michigan State University
Message-ID: <a5fs6c$2cir$1@msunews.cl.msu.edu>
References: <a48p2k$nop$1@nh.pace.co.uk> <3C76EE71.40506@telepath.com>
NNTP-Posting-Host: schubert.cse.msu.edu
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
Xref: archiver1.google.com comp.lang.ada:20453
Date: 2002-02-26T06:52:36-05:00
List-Id: <comp.lang.ada>

I remembering that there was a discussion about using quicksort for these
list components.  There was naturally concern about the O(n^2) worst case
performance.  If people are still worried about this issue, I have a
solution that guarantees that quicksort worst case is O(n*log n).  Before
any of you spill your coffee ;-) there is a hefty constant involved that
makes this modified quicksort slower on average than heapsort (maybe
mergesort sort also but it doesn't take more space that mergesort).  Anyway
the idea is to choose the median of each list (sublist) in linear time.
There happens to be a 'well known algorithm' for this.  The only drawback is
a hit on the constant.  I figure it might not be too bad of a price to pay,
though.

Comments?

-CRM