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

[bdowning-oU/tDdhfGLReoWH0uzbU5w@public.gmane.org (Brian Downing)]

On Tue, Feb 05, 2008 at 10:21:58PM +0000, Johannes Schindelin wrote:
> On Tue, 5 Feb 2008, Brian Downing wrote:
> > diff --git a/compat/qsort.c b/compat/qsort.c
> > new file mode 100644
> > index 0000000..8663889
> > --- /dev/null
> > +++ b/compat/qsort.c
> > @@ -0,0 +1,60 @@
> > +#include "../git-compat-util.h"
> > +
> > +/* This merge sort implementation is simplified from glibc's. */
> > +static void msort_with_tmp(void *b, size_t n, size_t s,
> 
> Didn't you forget to include the original copyright, as well as yours?

I (perhaps naïvely) assumed the "from glibc" would be enough.  If not,
the original is:

/* An alternative to qsort, with an identical interface.
   This file is part of the GNU C Library.
   Copyright (C) 1992,95-97,99,2000,01,02,04 Free Software Foundation, Inc.
   Written by Mike Haertel, September 1988.

   The GNU C Library is free software; you can redistribute it and/or
   modify it under the terms of the GNU Lesser General Public
   License as published by the Free Software Foundation; either
   version 2.1 of the License, or (at your option) any later version.

   The GNU C Library is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   Lesser General Public License for more details.

   You should have received a copy of the GNU Lesser General Public
   License along with the GNU C Library; if not, write to the Free
   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
   02111-1307 USA.  */

(That was from glibc-2.3.6/stdlib/msort.c.  I'm not sure of the exact
version I referenced for the implementation, but it was a lot closer to
2.3.6 than the current 2.7.)

As far as my copyleft, I was just planning on it being under Git's
blanket copyleft.  I really only pruned and reformatted code; there's
really nothing substantial to claim ownership of.

> BTW if these 60 lines have code that is really faster than Microsoft's 
> implementation of a sort, it is really fascinating to me.

Well, it's faster for us, but I bet our (usually mostly-sorted) tree
input is just better for a sort like a merge sort rather than a
quicksort.

-bcd