Re: [PATCH] compat: Add simplified merge sort implementation from glibc

["Mike Ralphson" <mike.ralphson-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>]

On Feb 3, 2008 4:50 AM, Brian Downing <bdowning-oU/tDdhfGLReoWH0uzbU5w@public.gmane.org> wrote:
> On Sun, Feb 03, 2008 at 02:37:27AM +0000, Johannes Schindelin wrote:
> > I should add that this is a stripped-down version of glibc's sort() (yes,
> > the GPL of glibc allows that we rip it, for all you license wieners out
> > there).
> >
> > AFAIR the discussion about the different implementations of a sort
> > algorithm boiled down to one particular implementation being quicker than
> > what this patch has, but with dubious licensing, and the glibc
> > implementation without the modifications present in this patch being
> > slower.
> >
> > So I would like this to go in, evidently, if only as a starting point for
> > people to play with sorting algorithms, to find the one which is optimal
> > for our general use (we have quite some uses where we put in _almost_
> > sorted data, which seems to be the worst-case for many sorting
> > algorithms).
>
> If this is what I am thinking of, the sort of dubious licensing was
> faster than glibc's quicksort.  This patch, however, is simplified from
> glibc's mergesort (which is what glibc uses for the qsort() call except
> for very large arrays), and was determined to be faster than both.
>
> See:
>
> http://groups.google.com/group/msysgit/browse_frm/thread/3c2eb564b9d0a994
>
> and the links from that thread for more information.

Tested-by: Mike Ralphson <mike.ralphson-Re5JQEeQqe8AvxtiuMwx3w@public.gmane.org>

Many thanks Brian, I held off from submitting your patch to git.git
because of the 1.5.4 freeze. I'll retest my other candidate qsort
implementations and report back. For now this makes git look good on
AIX. It would be good to have feedback from users of older versions of
Solaris too.

Once the final patch is in, I'll drop some queued AIX Makefile patches on top.

Cheers, Mike