Hi,

On Sat, 2 Feb 2008, Brian Downing wrote:

quoted text
> 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@lavos.net>
> Signed-off-by: Steffen Prohaska <prohaska@zib.de>
> Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de>

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

-
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