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

On Tue, Feb 05, 2008 at 10:21:58PM +0000, Johannes Schindelin wrote:

On Tue, 5 Feb 2008, Brian Downing wrote:

quoted

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