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
> seiw...@perforce.com f-f-f-fast SCM http://www.perforce.com
>
>
>
> To Unsubscribe: send mail to majord...@freebsd.org
> with "unsubscribe freebsd-hackers" in the body of the message
>
To Unsubscribe: send mail to majord...@freebsd.org
with "unsubscribe freebsd-hackers" in the body of the message
