This is the mail archive of the
libc-alpha@sourceware.org
mailing list for the glibc project.
Re: quicksort
* Carlos O'Donell [2011-11-29 13:24 -0500]:
> On 11/29/2011 12:49 PM, Carsten Hey wrote:
> > Carlos O'Donell suggested talking about the code first before stating
> > with the paperwork. I think this is a sane suggestion.
>
> FYI.
>
> I do not want to encourage anyone to look at Carsten's patches, doing so
> would immediately cause copyright problems if that person was involved
> in related glibc work *before* copyright is acquired for the changes.
Ok, then I misinterpreted what you wrote.
So the way of proceeding seems to be first doing the paperwork after it
has been ensured that my patches and my original implementations are
really different works or whatever, as explained in a previous mail and
then possibly merging into your tree.
> We can however talk about the current glibc code and what's wrong with it
> and possibly what to do about it.
Problems addressed by my patches are:
* It fails to sort for example {2,0,0,1,2,0,0}. This is hidden by
running insertion sort over the whole array.
* Multisets are not sorted faster than random data.
* The median selection is suboptimal if a lot of elements are going to
be partitioned. Using pseudo-median of nine instead leads to
a better pivot on average.
* Median of three selection swaps without a need to on inversely sorted
data.
* Swapping is slow.
Regards
Carsten