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

On Feb 3, 2008 4:50 AM, Brian Downing [off-list ref] wrote:

On Sun, Feb 03, 2008 at 02:37:27AM +0000, Johannes Schindelin wrote:

quoted

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 <redacted>

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