From owner-freebsd-hackers Wed Aug 18 17:36:14 1999 Delivered-To: freebsd-hackers@freebsd.org Received: from bubba.whistle.com (bubba.whistle.com [207.76.205.7]) by hub.freebsd.org (Postfix) with ESMTP id 1F39615B60 for ; Wed, 18 Aug 1999 17:35:31 -0700 (PDT) (envelope-from archie@whistle.com) Received: (from archie@localhost) by bubba.whistle.com (8.9.2/8.9.2) id RAA36248; Wed, 18 Aug 1999 17:35:37 -0700 (PDT) From: Archie Cobbs Message-Id: <199908190035.RAA36248@bubba.whistle.com> Subject: Re: anybody love qsort.c? In-Reply-To: <199908182356.QAA09187@perforce.com> from Christopher Seiwald at "Aug 18, 1999 04:56:48 pm" To: seiwald@perforce.com (Christopher Seiwald) Date: Wed, 18 Aug 1999 17:35:37 -0700 (PDT) Cc: freebsd-hackers@FreeBSD.ORG X-Mailer: ELM [version 2.4ME+ PL54 (25)] MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Sender: owner-freebsd-hackers@FreeBSD.ORG Precedence: bulk X-Loop: FreeBSD.ORG Christopher Seiwald writes: > The FreeBSD qsort implementation has a rather nasty degenerate case. > If you have data that partitions exactly about the median pivot, yet > which is unsorted in either partition, you get get treated to an insertion > sort. Example: > > 1 2 3 4 5 6 7 8 9 10 19 18 17 16 14 14 13 12 11 > > qsort picks 10 as the median, does no swaps on its first pass, and so > decides to switch to an insertion sort. The idea is that if no swaps > occur, the data is likely to be nearly already sorted and a good candidate > for insertion sort. This turns out to be a (very) bad idea if you have > some unsorted data buried in the middle of a (very) large dataset. > > The implementation claims to come from Bentley and McIlroy's paper, > "Engineering a Sort Function," and this is largely true, but the insertion > sort optimization(?) isn't in that paper. The GNU qsort.c only does an > insertion sort if it is below a certain threshhold in size, and so never > attempts such a sort on the whole dataset. (The GNU qsort does a number > of other things pooh-poohed in the Bentley paper.) > > It's a pretty straightforward change to bypass the insertion sort for > large subsets of the data. If no one has a strong love for qsort, I'll > educate myself on how to make and contribute this change. Sounds good to me.. let's fix it. -Archie ___________________________________________________________________________ Archie Cobbs * Whistle Communications, Inc. * http://www.whistle.com To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message