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

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