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.