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

Hi,

On Sat, 2 Feb 2008, Brian Downing 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.

Yeah, sorry, I forgot that important fact.

Thanks,
Dscho