Date: Thu, 19 Aug 1999 18:16:38 +0300 (EEST) From: Narvi <narvi@haldjas.folklore.ee> To: Christopher Seiwald <seiwald@perforce.com> Cc: freebsd-hackers@FreeBSD.ORG Subject: Re: anybody love qsort.c? Message-ID: <Pine.BSF.3.96.990819181348.19879V-100000@haldjas.folklore.ee> In-Reply-To: <199908182356.QAA09187@perforce.com>
next in thread | previous in thread | raw e-mail | index | archive | help
Doesn't the qsort just switch to isort *if* the partition to sort is short enough? Got to check it out, but afaik the size at that qsorts switch to isort is usually between 8 and 24, with 16 being most common - both halfs are shorter than 16, so they get isorted. Sander There is no love, no good, no happiness and no future - all these are just illusions. On Wed, 18 Aug 1999, Christopher Seiwald wrote: > 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. > > Christopher > ---- > Christopher Seiwald Perforce Software 1-510-864-7400 > seiwald@perforce.com f-f-f-fast SCM http://www.perforce.com > > > > To Unsubscribe: send mail to majordomo@FreeBSD.org > with "unsubscribe freebsd-hackers" in the body of the message > To Unsubscribe: send mail to majordomo@FreeBSD.org with "unsubscribe freebsd-hackers" in the body of the message
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?Pine.BSF.3.96.990819181348.19879V-100000>