Re: qsort again (was Re: Strange Create Index

On Wed, Feb 15, 2006 at 11:30:54PM -0500, Ron wrote:
> Even better (and more easily scaled as the number of GPR's in the CPU
> changes) is to use
> the set {L; L+1; L+2; t>>1; R-2; R-1; R}
> This means that instead of 7 random memory accesses, we have 3; two
> of which result in a
> burst access for three elements each.

Isn't that improvement going to disappear competely if you choose a bad
pivot?

> SIDE NOTE: IIRC glibc's qsort is actually merge sort. Merge sort
> performance is insensitive to all inputs, and there are way to
> optimize it as well.

glibc-2.3.5/stdlib/qsort.c:

/* Order size using quicksort. This implementation incorporates
four optimizations discussed in Sedgewick:

I can't see any references to merge sort in there at all.

/* Steinar */
--
Homepage: http://www.sesse.net/