On Sun, Feb 03, 2008 at 02:37:27AM +0000, Johannes Schindelin wrote:
quoted text
> 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.

-bcd
-
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html