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

From: Johannes Schindelin <johannes.schindelin-mmb7mzphnfy@public.gmane.org>
Date: Feb 3, 2008, 02:37 UTC
Message-ID: <alpine.LSU.1.00.0802030231080.7372@racer.site>
In-Reply-To: <20080203011130.GK26392-oU/tDdhfGLReoWH0uzbU5w@public.gmane.org>

Hi,

On Sat, 2 Feb 2008, Brian Downing wrote:

Show 28 quoted lines

> qsort in Windows 2000 (and possibly other older Windows' C libraries)
> is a Quicksort with the usual O(n^2) worst case.  Unfortunately, sorting
> Git trees seems to get very close to that worst case quite often:
> 
>     $ /git/gitbad runstatus
>     # On branch master
>     qsort, nmemb = 30842
>     done, 237838087 comparisons.
> 
> This patch adds a simplified version of the merge sort that is glibc's
> qsort(3).  As a merge sort, this needs a temporary array equal in size
> to the array that is to be sorted.
> 
> The complexity that was removed is:
> 
> * Doing direct stores for word-size and -aligned data.
> * Falling back to quicksort if the allocation required to perform the
>   merge sort would likely push the machine into swap.
> 
> Even with these simplifications, this seems to outperform the Windows
> qsort(3) implementation, even in Windows XP (where it is "fixed" and
> doesn't trigger O(n^2) complexity on trees).
> 
> [jes: moved into compat/qsort.c, as per Johannes Sixt's suggestion]
> 
> Signed-off-by: Brian Downing <bdowning-oU/tDdhfGLReoWH0uzbU5w@public.gmane.org>
> Signed-off-by: Steffen Prohaska <prohaska-wjoc1KHpMeg@public.gmane.org>
> Signed-off-by: Johannes Schindelin <johannes.schindelin-Mmb7MZpHnFY@public.gmane.org>

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

Ciao, Dscho