Change the internal implementation of sort() to be mergesort

instead of quicksort, from John Linderman <jpl@research.att.com>.
Gives us better worst case, better average case, and stability.
What's there not to like?  (Small fixes for threaded builds
were required).

p4raw-id: //depot/perl@6927

1 files changed, 332 insertions, 632 deletions

diff --git a/pp_ctl.c b/pp_ctl.c
index 45f9a7e2a3..01b8fec909 100644
--- a/pp_ctl.c
+++ b/pp_ctl.c
@@ -3672,683 +3672,383 @@ S_doparseform(pTHX_ SV *sv)
     SvCOMPILED_on(sv);
 }
 
-/*
- * The rest of this file was derived from source code contributed
- * by Tom Horsley.
- *
- * NOTE: this code was derived from Tom Horsley's qsort replacement
- * and should not be confused with the original code.
- */
-
-/* Copyright (C) Tom Horsley, 1997. All rights reserved.
-
-   Permission granted to distribute under the same terms as perl which are
-   (briefly):
-
-    This program is free software; you can redistribute it and/or modify
-    it under the terms of either:
 
-	a) the GNU General Public License as published by the Free
-	Software Foundation; either version 1, or (at your option) any
-	later version, or
+#ifdef	TESTHARNESS
+#include <sys/types.h>
+typedef	void SV;
+#define pTHXo_
+#define pTHX_
+#define STATIC
+#define New(ID,VAR,N,TYPE) VAR=(TYPE *)malloc((N)*sizeof(TYPE))
+#define	Safefree(VAR) free(VAR)
+typedef int  (*SVCOMPARE_t) (pTHXo_ SV*, SV*);
+#endif	/* TESTHARNESS */
+
+typedef char * aptr;		/* pointer for arithmetic on sizes */
+typedef SV * gptr;		/* pointers in our lists */
+
+/* Copyright notice from Peter's original sort,
+** which has been modified heavily.  Good ideas are Peter's
+** bugs are jpl's
+*/
 
-	b) the "Artistic License" which comes with this Kit.
+/* Much of this code is original source code from BSD4.4, and is 
+ * copyright (c) 1991 The Regents of the University of California.
+ *
+ * 1. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ * 2. All advertising materials mentioning features or use of this software
+ *    must display the following acknowledgement:
+ *	This product includes software developed by the University of
+ *	California, Berkeley and its contributors.
+ * 3. Neither the name of the University nor the names of its contributors
+ *    may be used to endorse or promote products derived from this software
+ *    without specific prior written permission.
+ *
+*/
 
-   Details on the perl license can be found in the perl source code which
-   may be located via the www.perl.com web page.
+/* 
+ * AUTHOR: Peter McIlroy
+ * 1991-1992,  See: Optimistic Merge Sort (SODA '92)
+*/
 
-   This is the most wonderfulest possible qsort I can come up with (and
-   still be mostly portable) My (limited) tests indicate it consistently
-   does about 20% fewer calls to compare than does the qsort in the Visual
-   C++ library, other vendors may vary.
+/* Binary merge internal sort, with a few special mods
+** for the special perl environment it now finds itself in.
+**
+** Things that were once options have been hotwired
+** to values suitable for this use.  In particular, we'll always
+** initialize looking for natural runs, we'll always produce stable
+** output, and we'll always do Peter McIlroy's binary merge.
+*/
 
-   Some of the ideas in here can be found in "Algorithms" by Sedgewick,
-   others I invented myself (or more likely re-invented since they seemed
-   pretty obvious once I watched the algorithm operate for a while).
+/* Pointer types for arithmetic and storage and convenience casts */
 
-   Most of this code was written while watching the Marlins sweep the Giants
-   in the 1997 National League Playoffs - no Braves fans allowed to use this
-   code (just kidding :-).
+#define	APTR(P)	((aptr)(P))
+#define	GPTP(P)	((gptr *)(P))
+#define GPPP(P) ((gptr **)(P))
 
-   I realize that if I wanted to be true to the perl tradition, the only
-   comment in this file would be something like:
 
-   ...they shuffled back towards the rear of the line. 'No, not at the
-   rear!'  the slave-driver shouted. 'Three files up. And stay there...
+/* byte offset from pointer P to (larger) pointer Q */
+#define	BYTEOFF(P, Q) (APTR(Q) - APTR(P))
 
-   However, I really needed to violate that tradition just so I could keep
-   track of what happens myself, not to mention some poor fool trying to
-   understand this years from now :-).
-*/
+#define PSIZE sizeof(gptr)
 
-/* ********************************************************** Configuration */
+/* If PSIZE is power of 2, make PSHIFT that power, if that helps */
 
-#ifndef QSORT_ORDER_GUESS
-#define QSORT_ORDER_GUESS 2	/* Select doubling version of the netBSD trick */
+#ifdef	PSHIFT
+#define	PNELEM(P, Q)	(BYTEOFF(P,Q) >> (PSHIFT))
+#define	PNBYTE(N)	((N) << (PSHIFT))
+#define	PINDEX(P, N)	(GPTP(APTR(P) + PNBYTE(N)))
+#else
+/* Leave optimization to compiler */
+#define	PNELEM(P, Q)	(GPTP(Q) - GPTP(P))
+#define	PNBYTE(N)	((N) * (PSIZE))
+#define	PINDEX(P, N)	(GPTP(P) + (N))
 #endif
 
-/* QSORT_MAX_STACK is the largest number of partitions that can be stacked up for
-   future processing - a good max upper bound is log base 2 of memory size
-   (32 on 32 bit machines, 64 on 64 bit machines, etc). In reality can
-   safely be smaller than that since the program is taking up some space and
-   most operating systems only let you grab some subset of contiguous
-   memory (not to mention that you are normally sorting data larger than
-   1 byte element size :-).
-*/
-#ifndef QSORT_MAX_STACK
-#define QSORT_MAX_STACK 32
-#endif
+/* Pointer into other corresponding to pointer into this */
+#define	POTHER(P, THIS, OTHER) GPTP(APTR(OTHER) + BYTEOFF(THIS,P))
 
-/* QSORT_BREAK_EVEN is the size of the largest partition we should insertion sort.
-   Anything bigger and we use qsort. If you make this too small, the qsort
-   will probably break (or become less efficient), because it doesn't expect
-   the middle element of a partition to be the same as the right or left -
-   you have been warned).
-*/
-#ifndef QSORT_BREAK_EVEN
-#define QSORT_BREAK_EVEN 6
-#endif
+#define FROMTOUPTO(src, dst, lim) do *dst++ = *src++; while(src<lim)
 
-/* ************************************************************* Data Types */
 
-/* hold left and right index values of a partition waiting to be sorted (the
-   partition includes both left and right - right is NOT one past the end or
-   anything like that).
+/* Runs are identified by a pointer in the auxilliary list.
+** The pointer is at the start of the list,
+** and it points to the start of the next list.
+** NEXT is used as an lvalue, too.
 */
-struct partition_stack_entry {
-   int left;
-   int right;
-#ifdef QSORT_ORDER_GUESS
-   int qsort_break_even;
-#endif
-};
 
-/* ******************************************************* Shorthand Macros */
+#define	NEXT(P)		(*GPPP(P))
 
-/* Note that these macros will be used from inside the qsort function where
-   we happen to know that the variable 'elt_size' contains the size of an
-   array element and the variable 'temp' points to enough space to hold a
-   temp element and the variable 'array' points to the array being sorted
-   and 'compare' is the pointer to the compare routine.
 
-   Also note that there are very many highly architecture specific ways
-   these might be sped up, but this is simply the most generally portable
-   code I could think of.
+/* PTHRESH is the minimum number of pairs with the same sense to justify
+** checking for a run and extending it.  Note that PTHRESH counts PAIRS,
+** not just elements, so PTHRESH == 8 means a run of 16.
 */
 
-/* Return < 0 == 0 or > 0 as the value of elt1 is < elt2, == elt2, > elt2
-*/
-#define qsort_cmp(elt1, elt2) \
-   ((*compare)(aTHXo_ array[elt1], array[elt2]))
+#define	PTHRESH (8)
 
-#ifdef QSORT_ORDER_GUESS
-#define QSORT_NOTICE_SWAP swapped++;
-#else
-#define QSORT_NOTICE_SWAP
-#endif
-
-/* swaps contents of array elements elt1, elt2.
-*/
-#define qsort_swap(elt1, elt2) \
-   STMT_START { \
-      QSORT_NOTICE_SWAP \
-      temp = array[elt1]; \
-      array[elt1] = array[elt2]; \
-      array[elt2] = temp; \
-   } STMT_END
-
-/* rotate contents of elt1, elt2, elt3 such that elt1 gets elt2, elt2 gets
-   elt3 and elt3 gets elt1.
+/* RTHRESH is the number of elements in a run that must compare low
+** to the low element from the opposing run before we justify
+** doing a binary rampup instead of single stepping.
+** In random input, N in a row low should only happen with
+** probability 2^(1-N), so we can risk that we are dealing
+** with orderly input without paying much when we aren't.
 */
-#define qsort_rotate(elt1, elt2, elt3) \
-   STMT_START { \
-      QSORT_NOTICE_SWAP \
-      temp = array[elt1]; \
-      array[elt1] = array[elt2]; \
-      array[elt2] = array[elt3]; \
-      array[elt3] = temp; \
-   } STMT_END
 
-/* ************************************************************ Debug stuff */
+#define RTHRESH (6)
 
-#ifdef QSORT_DEBUG
 
-static void
-break_here()
-{
-   return; /* good place to set a breakpoint */
-}
+/*
+** Overview of algorithm and variables.
+** The array of elements at list1 will be organized into runs of length 2,
+** or runs of length >= 2 * PTHRESH.  We only try to form long runs when
+** PTHRESH adjacent pairs compare in the same way, suggesting overall order.
+**
+** Unless otherwise specified, pair pointers address the first of two elements.
+**
+** b and b+1 are a pair that compare with sense ``sense''.
+** b is the ``bottom'' of adjacent pairs that might form a longer run.
+**
+** p2 parallels b in the list2 array, where runs are defined by
+** a pointer chain.
+**
+** t represents the ``top'' of the adjacent pairs that might extend
+** the run beginning at b.  Usually, t addresses a pair
+** that compares with opposite sense from (b,b+1).
+** However, it may also address a singleton element at the end of list1,
+** or it may be equal to ``last'', the first element beyond list1.
+**
+** r addresses the Nth pair following b.  If this would be beyond t,
+** we back it off to t.  Only when r is less than t do we consider the
+** run long enough to consider checking.
+**
+** q addresses a pair such that the pairs at b through q already form a run.
+** Often, q will equal b, indicating we only are sure of the pair itself.
+** However, a search on the previous cycle may have revealed a longer run,
+** so q may be greater than b.
+**
+** p is used to work back from a candidate r, trying to reach q,
+** which would mean b through r would be a run.  If we discover such a run,
+** we start q at r and try to push it further towards t.
+** If b through r is NOT a run, we detect the wrong order at (p-1,p).
+** In any event, after the check (if any), we have two main cases.
+**
+** 1) Short run.  b <= q < p <= r <= t.
+**	b through q is a run (perhaps trivial)
+**	q through p are uninteresting pairs
+**	p through r is a run
+**
+** 2) Long run.  b < r <= q < t.
+**	b through q is a run (of length >= 2 * PTHRESH)
+**
+** Note that degenerate cases are not only possible, but likely.
+** For example, if the pair following b compares with opposite sense,
+** then b == q < p == r == t.
+*/
 
-#define qsort_assert(t) (void)( (t) || (break_here(), 0) )
 
 static void
-doqsort_all_asserts(
-   void * array,
-   size_t num_elts,
-   size_t elt_size,
-   int (*compare)(const void * elt1, const void * elt2),
-   int pc_left, int pc_right, int u_left, int u_right)
+dynprep(pTHX_ gptr *list1, gptr *list2, size_t nmemb, SVCOMPARE_t cmp)
 {
-   int i;
-
-   qsort_assert(pc_left <= pc_right);
-   qsort_assert(u_right < pc_left);
-   qsort_assert(pc_right < u_left);
-   for (i = u_right + 1; i < pc_left; ++i) {
-      qsort_assert(qsort_cmp(i, pc_left) < 0);
-   }
-   for (i = pc_left; i < pc_right; ++i) {
-      qsort_assert(qsort_cmp(i, pc_right) == 0);
-   }
-   for (i = pc_right + 1; i < u_left; ++i) {
-      qsort_assert(qsort_cmp(pc_right, i) < 0);
-   }
+    int sense;
+    register gptr *b, *p, *q, *t, *p2;
+    register gptr c, *last, *r;
+    gptr *savep;
+
+    b = list1;
+    last = PINDEX(b, nmemb);
+    sense = (cmp(aTHX_ *b, *(b+1)) > 0);
+    for (p2 = list2; b < last; ) {
+	/* We just started, or just reversed sense.
+	** Set t at end of pairs with the prevailing sense.
+	*/
+	for (p = b+2, t = p; ++p < last; t = ++p) {
+	    if ((cmp(aTHX_ *t, *p) > 0) != sense) break;
+	}
+	q = b;
+	/* Having laid out the playing field, look for long runs */
+	do {
+	    p = r = b + (2 * PTHRESH);
+	    if (r >= t) p = r = t;	/* too short to care about */
+	    else {
+		while (((cmp(aTHX_ *(p-1), *p) > 0) == sense) &&
+		       ((p -= 2) > q));
+		if (p <= q) {
+		    /* b through r is a (long) run.
+		    ** Extend it as far as possible.
+		    */
+		    p = q = r;
+		    while (((p += 2) < t) &&
+			   ((cmp(aTHX_ *(p-1), *p) > 0) == sense)) q = p;
+		    r = p = q + 2;	/* no simple pairs, no after-run */
+		}
+	    }
+	    if (q > b) {		/* run of greater than 2 at b */
+		savep = p;
+		p = q += 2;
+		/* pick up singleton, if possible */
+		if ((p == t) &&
+		    ((t + 1) == last) &&
+		    ((cmp(aTHX_ *(p-1), *p) > 0) == sense))
+		    savep = r = p = q = last;
+		p2 = NEXT(p2) = p2 + (p - b);
+		if (sense) while (b < --p) {
+		    c = *b;
+		    *b++ = *p;
+		    *p = c;
+		}
+		p = savep;
+	    }
+	    while (q < p) {		/* simple pairs */
+		p2 = NEXT(p2) = p2 + 2;
+		if (sense) {
+		    c = *q++;
+		    *(q-1) = *q;
+		    *q++ = c;
+		} else q += 2;
+	    }
+	    if (((b = p) == t) && ((t+1) == last)) {
+		NEXT(p2) = p2 + 1;
+		b++;
+	    }
+	    q = r;
+	} while (b < t);
+	sense = !sense;
+    }
+    return;
 }
 
-#define qsort_all_asserts(PC_LEFT, PC_RIGHT, U_LEFT, U_RIGHT) \
-   doqsort_all_asserts(array, num_elts, elt_size, compare, \
-                 PC_LEFT, PC_RIGHT, U_LEFT, U_RIGHT)
-
-#else
 
-#define qsort_assert(t) ((void)0)
+/* Overview of bmerge variables:
+**
+** list1 and list2 address the main and auxiliary arrays.
+** They swap identities after each merge pass.
+** Base points to the original list1, so we can tell if
+** the pointers ended up where they belonged (or must be copied).
+**
+** When we are merging two lists, f1 and f2 are the next elements
+** on the respective lists.  l1 and l2 mark the end of the lists.
+** tp2 is the current location in the merged list.
+**
+** p1 records where f1 started.
+** After the merge, a new descriptor is built there.
+**
+** p2 is a ``parallel'' pointer in (what starts as) descriptor space.
+** It is used to identify and delimit the runs.
+**
+** In the heat of determining where q, the greater of the f1/f2 elements,
+** belongs in the other list, b, t and p, represent bottom, top and probe
+** locations, respectively, in the other list.
+** They make convenient temporary pointers in other places.
+*/
 
-#define qsort_all_asserts(PC_LEFT, PC_RIGHT, U_LEFT, U_RIGHT) ((void)0)
+STATIC void
+S_qsortsv(pTHX_ gptr *list1, size_t nmemb, SVCOMPARE_t cmp)
+{
+    int i, run;
+    int sense;
+    register gptr *f1, *f2, *t, *b, *p, *tp2, *l1, *l2, *q;
+    gptr *aux, *list2, *p2, *last;
+    gptr *base = list1;
+    gptr *p1;
+
+    if (nmemb <= 1) return;	/* sorted trivially */
+    New(799,list2,nmemb,gptr);	/* allocate auxilliary array */
+    aux = list2;
+    dynprep(aTHX_ list1, list2, nmemb, cmp);
+    last = PINDEX(list2, nmemb);
+    while (NEXT(list2) != last) {
+	/* More than one run remains.  Do some merging to reduce runs. */
+	l2 = p1 = list1;
+	for (tp2 = p2 = list2; p2 != last;) {
+	    /* The new first run begins where the old second list ended.
+	    ** Use the p2 ``parallel'' pointer to identify the end of the run.
+	    */
+	    f1 = l2;
+	    t = NEXT(p2);
+	    f2 = l1 = POTHER(t, list2, list1);
+	    if (t != last) t = NEXT(t);
+	    l2 = POTHER(t, list2, list1);
+	    p2 = t;
+	    while (f1 < l1 && f2 < l2) {
+		/* If head 1 is larger than head 2, find ALL the elements
+		** in list 2 strictly less than head1, write them all,
+		** then head 1.  Then compare the new heads, and repeat,
+		** until one or both lists are exhausted.
+		**
+		** In all comparisons (after establishing
+		** which head to merge) the item to merge
+		** (at pointer q) is the first operand of
+		** the comparison.  When we want to know
+		** if ``q is strictly less than the other'',
+		** we can't just do
+		**    cmp(q, other) < 0
+		** because stability demands that we treat equality
+		** as high when q comes from l2, and as low when
+		** q was from l1.  So we ask the question by doing
+		**    cmp(q, other) <= sense
+		** and make sense == 0 when equality should look low,
+		** and -1 when equality should look high.
+		*/
+
+
+		if (cmp(aTHX_ *f1, *f2) <= 0) {
+		    q = f2; b = f1; t = l1;
+		    sense = -1;
+		} else {
+		    q = f1; b = f2; t = l2;
+		    sense = 0;
+		}
 
-#endif
 
-/* ****************************************************************** qsort */
+		/* ramp up
+		**
+		** Leave t at something strictly
+		** greater than q (or at the end of the list),
+		** and b at something strictly less than q.
+		*/
+		for (i = 1, run = 0 ;;) {
+		    if ((p = PINDEX(b, i)) >= t) {
+			/* off the end */
+			if (((p = PINDEX(t, -1)) > b) &&
+			    (cmp(aTHX_ *q, *p) <= sense))
+			     t = p;
+			else b = p;
+			break;
+		    } else if (cmp(aTHX_ *q, *p) <= sense) {
+			t = p;
+			break;
+		    } else b = p;
+		    if (++run >= RTHRESH) i += i;
+		}
 
-STATIC void
-S_qsortsv(pTHX_ SV ** array, size_t num_elts, SVCOMPARE_t compare)
-{
-   register SV * temp;
 
-   struct partition_stack_entry partition_stack[QSORT_MAX_STACK];
-   int next_stack_entry = 0;
+		/* q is known to follow b and must be inserted before t.
+		** Increment b, so the range of possibilities is [b,t).
+		** Round binary split down, to favor early appearance.
+		** Adjust b and t until q belongs just before t.
+		*/
 
-   int part_left;
-   int part_right;
-#ifdef QSORT_ORDER_GUESS
-   int qsort_break_even;
-   int swapped;
-#endif
+		b++;
+		while (b < t) {
+		    p = PINDEX(b, (PNELEM(b, t) - 1) / 2);
+		    if (cmp(aTHX_ *q, *p) <= sense) {
+			t = p;
+		    } else b = p + 1;
+		}
 
-   /* Make sure we actually have work to do.
-   */
-   if (num_elts <= 1) {
-      return;
-   }
-
-   /* Setup the initial partition definition and fall into the sorting loop
-   */
-   part_left = 0;
-   part_right = (int)(num_elts - 1);
-#ifdef QSORT_ORDER_GUESS
-   qsort_break_even = QSORT_BREAK_EVEN;
-#else
-#define qsort_break_even QSORT_BREAK_EVEN
-#endif
-   for ( ; ; ) {
-      if ((part_right - part_left) >= qsort_break_even) {
-         /* OK, this is gonna get hairy, so lets try to document all the
-            concepts and abbreviations and variables and what they keep
-            track of:
-
-            pc: pivot chunk - the set of array elements we accumulate in the
-                middle of the partition, all equal in value to the original
-                pivot element selected. The pc is defined by:
-
-                pc_left - the leftmost array index of the pc
-                pc_right - the rightmost array index of the pc
-
-                we start with pc_left == pc_right and only one element
-                in the pivot chunk (but it can grow during the scan).
-
-            u:  uncompared elements - the set of elements in the partition
-                we have not yet compared to the pivot value. There are two
-                uncompared sets during the scan - one to the left of the pc
-                and one to the right.
-
-                u_right - the rightmost index of the left side's uncompared set
-                u_left - the leftmost index of the right side's uncompared set
-
-                The leftmost index of the left sides's uncompared set
-                doesn't need its own variable because it is always defined
-                by the leftmost edge of the whole partition (part_left). The
-                same goes for the rightmost edge of the right partition
-                (part_right).
-
-                We know there are no uncompared elements on the left once we
-                get u_right < part_left and no uncompared elements on the
-                right once u_left > part_right. When both these conditions
-                are met, we have completed the scan of the partition.
-
-                Any elements which are between the pivot chunk and the
-                uncompared elements should be less than the pivot value on
-                the left side and greater than the pivot value on the right
-                side (in fact, the goal of the whole algorithm is to arrange
-                for that to be true and make the groups of less-than and
-                greater-then elements into new partitions to sort again).
-
-            As you marvel at the complexity of the code and wonder why it
-            has to be so confusing. Consider some of the things this level
-            of confusion brings:
-
-            Once I do a compare, I squeeze every ounce of juice out of it. I
-            never do compare calls I don't have to do, and I certainly never
-            do redundant calls.
-
-            I also never swap any elements unless I can prove there is a
-            good reason. Many sort algorithms will swap a known value with
-            an uncompared value just to get things in the right place (or
-            avoid complexity :-), but that uncompared value, once it gets
-            compared, may then have to be swapped again. A lot of the
-            complexity of this code is due to the fact that it never swaps
-            anything except compared values, and it only swaps them when the
-            compare shows they are out of position.
-         */
-         int pc_left, pc_right;
-         int u_right, u_left;
-
-         int s;
-
-         pc_left = ((part_left + part_right) / 2);
-         pc_right = pc_left;
-         u_right = pc_left - 1;
-         u_left = pc_right + 1;
-
-         /* Qsort works best when the pivot value is also the median value
-            in the partition (unfortunately you can't find the median value
-            without first sorting :-), so to give the algorithm a helping
-            hand, we pick 3 elements and sort them and use the median value
-            of that tiny set as the pivot value.
-
-            Some versions of qsort like to use the left middle and right as
-            the 3 elements to sort so they can insure the ends of the
-            partition will contain values which will stop the scan in the
-            compare loop, but when you have to call an arbitrarily complex
-            routine to do a compare, its really better to just keep track of
-            array index values to know when you hit the edge of the
-            partition and avoid the extra compare. An even better reason to
-            avoid using a compare call is the fact that you can drop off the
-            edge of the array if someone foolishly provides you with an
-            unstable compare function that doesn't always provide consistent
-            results.
-
-            So, since it is simpler for us to compare the three adjacent
-            elements in the middle of the partition, those are the ones we
-            pick here (conveniently pointed at by u_right, pc_left, and
-            u_left). The values of the left, center, and right elements
-            are refered to as l c and r in the following comments.
-         */
-
-#ifdef QSORT_ORDER_GUESS
-         swapped = 0;
-#endif
-         s = qsort_cmp(u_right, pc_left);
-         if (s < 0) {
-            /* l < c */
-            s = qsort_cmp(pc_left, u_left);
-            /* if l < c, c < r - already in order - nothing to do */
-            if (s == 0) {
-               /* l < c, c == r - already in order, pc grows */
-               ++pc_right;
-               qsort_all_asserts(pc_left, pc_right, u_left + 1, u_right - 1);
-            } else if (s > 0) {
-               /* l < c, c > r - need to know more */
-               s = qsort_cmp(u_right, u_left);
-               if (s < 0) {
-                  /* l < c, c > r, l < r - swap c & r to get ordered */
-                  qsort_swap(pc_left, u_left);
-                  qsort_all_asserts(pc_left, pc_right, u_left + 1, u_right - 1);
-               } else if (s == 0) {
-                  /* l < c, c > r, l == r - swap c&r, grow pc */
-                  qsort_swap(pc_left, u_left);
-                  --pc_left;
-                  qsort_all_asserts(pc_left, pc_right, u_left + 1, u_right - 1);
-               } else {
-                  /* l < c, c > r, l > r - make lcr into rlc to get ordered */
-                  qsort_rotate(pc_left, u_right, u_left);
-                  qsort_all_asserts(pc_left, pc_right, u_left + 1, u_right - 1);
-               }
-            }
-         } else if (s == 0) {
-            /* l == c */
-            s = qsort_cmp(pc_left, u_left);
-            if (s < 0) {
-               /* l == c, c < r - already in order, grow pc */
-               --pc_left;
-               qsort_all_asserts(pc_left, pc_right, u_left + 1, u_right - 1);
-            } else if (s == 0) {
-               /* l == c, c == r - already in order, grow pc both ways */
-               --pc_left;
-               ++pc_right;
-               qsort_all_asserts(pc_left, pc_right, u_left + 1, u_right - 1);
-            } else {
-               /* l == c, c > r - swap l & r, grow pc */
-               qsort_swap(u_right, u_left);
-               ++pc_right;
-               qsort_all_asserts(pc_left, pc_right, u_left + 1, u_right - 1);
-            }
-         } else {
-            /* l > c */
-            s = qsort_cmp(pc_left, u_left);
-            if (s < 0) {
-               /* l > c, c < r - need to know more */
-               s = qsort_cmp(u_right, u_left);
-               if (s < 0) {
-                  /* l > c, c < r, l < r - swap l & c to get ordered */
-                  qsort_swap(u_right, pc_left);
-                  qsort_all_asserts(pc_left, pc_right, u_left + 1, u_right - 1);
-               } else if (s == 0) {
-                  /* l > c, c < r, l == r - swap l & c, grow pc */
-                  qsort_swap(u_right, pc_left);
-                  ++pc_right;
-                  qsort_all_asserts(pc_left, pc_right, u_left + 1, u_right - 1);
-               } else {
-                  /* l > c, c < r, l > r - rotate lcr into crl to order */
-                  qsort_rotate(u_right, pc_left, u_left);
-                  qsort_all_asserts(pc_left, pc_right, u_left + 1, u_right - 1);
-               }
-            } else if (s == 0) {
-               /* l > c, c == r - swap ends, grow pc */
-               qsort_swap(u_right, u_left);
-               --pc_left;
-               qsort_all_asserts(pc_left, pc_right, u_left + 1, u_right - 1);
-            } else {
-               /* l > c, c > r - swap ends to get in order */
-               qsort_swap(u_right, u_left);
-               qsort_all_asserts(pc_left, pc_right, u_left + 1, u_right - 1);
-            }
-         }
-         /* We now know the 3 middle elements have been compared and
-            arranged in the desired order, so we can shrink the uncompared
-            sets on both sides
-         */
-         --u_right;
-         ++u_left;
-         qsort_all_asserts(pc_left, pc_right, u_left, u_right);
-
-         /* The above massive nested if was the simple part :-). We now have
-            the middle 3 elements ordered and we need to scan through the
-            uncompared sets on either side, swapping elements that are on
-            the wrong side or simply shuffling equal elements around to get
-            all equal elements into the pivot chunk.
-         */
-
-         for ( ; ; ) {
-            int still_work_on_left;
-            int still_work_on_right;
-
-            /* Scan the uncompared values on the left. If I find a value
-               equal to the pivot value, move it over so it is adjacent to
-               the pivot chunk and expand the pivot chunk. If I find a value
-               less than the pivot value, then just leave it - its already
-               on the correct side of the partition. If I find a greater
-               value, then stop the scan.
-            */
-            while ((still_work_on_left = (u_right >= part_left))) {
-               s = qsort_cmp(u_right, pc_left);
-               if (s < 0) {
-                  --u_right;
-               } else if (s == 0) {
-                  --pc_left;
-                  if (pc_left != u_right) {
-                     qsort_swap(u_right, pc_left);
-                  }
-                  --u_right;
-               } else {
-                  break;
-               }
-               qsort_assert(u_right < pc_left);
-               qsort_assert(pc_left <= pc_right);
-               qsort_assert(qsort_cmp(u_right + 1, pc_left) <= 0);
-               qsort_assert(qsort_cmp(pc_left, pc_right) == 0);
-            }
 
-            /* Do a mirror image scan of uncompared values on the right
-            */
-            while ((still_work_on_right = (u_left <= part_right))) {
-               s = qsort_cmp(pc_right, u_left);
-               if (s < 0) {
-                  ++u_left;
-               } else if (s == 0) {
-                  ++pc_right;
-                  if (pc_right != u_left) {
-                     qsort_swap(pc_right, u_left);
-                  }
-                  ++u_left;
-               } else {
-                  break;
-               }
-               qsort_assert(u_left > pc_right);
-               qsort_assert(pc_left <= pc_right);
-               qsort_assert(qsort_cmp(pc_right, u_left - 1) <= 0);
-               qsort_assert(qsort_cmp(pc_left, pc_right) == 0);
-            }
+		/* Copy all the strictly low elements */
 
-            if (still_work_on_left) {
-               /* I know I have a value on the left side which needs to be
-                  on the right side, but I need to know more to decide
-                  exactly the best thing to do with it.
-               */
-               if (still_work_on_right) {
-                  /* I know I have values on both side which are out of
-                     position. This is a big win because I kill two birds
-                     with one swap (so to speak). I can advance the
-                     uncompared pointers on both sides after swapping both
-                     of them into the right place.
-                  */
-                  qsort_swap(u_right, u_left);
-                  --u_right;
-                  ++u_left;
-                  qsort_all_asserts(pc_left, pc_right, u_left, u_right);
-               } else {
-                  /* I have an out of position value on the left, but the
-                     right is fully scanned, so I "slide" the pivot chunk
-                     and any less-than values left one to make room for the
-                     greater value over on the right. If the out of position
-                     value is immediately adjacent to the pivot chunk (there
-                     are no less-than values), I can do that with a swap,
-                     otherwise, I have to rotate one of the less than values
-                     into the former position of the out of position value
-                     and the right end of the pivot chunk into the left end
-                     (got all that?).
-                  */
-                  --pc_left;
-                  if (pc_left == u_right) {
-                     qsort_swap(u_right, pc_right);
-                     qsort_all_asserts(pc_left, pc_right-1, u_left, u_right-1);
-                  } else {
-                     qsort_rotate(u_right, pc_left, pc_right);
-                     qsort_all_asserts(pc_left, pc_right-1, u_left, u_right-1);
-                  }
-                  --pc_right;
-                  --u_right;
-               }
-            } else if (still_work_on_right) {
-               /* Mirror image of complex case above: I have an out of
-                  position value on the right, but the left is fully
-                  scanned, so I need to shuffle things around to make room
-                  for the right value on the left.
-               */
-               ++pc_right;
-               if (pc_right == u_left) {
-                  qsort_swap(u_left, pc_left);
-                  qsort_all_asserts(pc_left+1, pc_right, u_left+1, u_right);
-               } else {
-                  qsort_rotate(pc_right, pc_left, u_left);
-                  qsort_all_asserts(pc_left+1, pc_right, u_left+1, u_right);
-               }
-               ++pc_left;
-               ++u_left;
-            } else {
-               /* No more scanning required on either side of partition,
-                  break out of loop and figure out next set of partitions
-               */
-               break;
-            }
-         }
-
-         /* The elements in the pivot chunk are now in the right place. They
-            will never move or be compared again. All I have to do is decide
-            what to do with the stuff to the left and right of the pivot
-            chunk.
-
-            Notes on the QSORT_ORDER_GUESS ifdef code:
-
-            1. If I just built these partitions without swapping any (or
-               very many) elements, there is a chance that the elements are
-               already ordered properly (being properly ordered will
-               certainly result in no swapping, but the converse can't be
-               proved :-).
-
-            2. A (properly written) insertion sort will run faster on
-               already ordered data than qsort will.
-
-            3. Perhaps there is some way to make a good guess about
-               switching to an insertion sort earlier than partition size 6
-               (for instance - we could save the partition size on the stack
-               and increase the size each time we find we didn't swap, thus
-               switching to insertion sort earlier for partitions with a
-               history of not swapping).
-
-            4. Naturally, if I just switch right away, it will make
-               artificial benchmarks with pure ascending (or descending)
-               data look really good, but is that a good reason in general?
-               Hard to say...
-         */
-
-#ifdef QSORT_ORDER_GUESS
-         if (swapped < 3) {
-#if QSORT_ORDER_GUESS == 1
-            qsort_break_even = (part_right - part_left) + 1;
-#endif
-#if QSORT_ORDER_GUESS == 2
-            qsort_break_even *= 2;
-#endif
-#if QSORT_ORDER_GUESS == 3
-            int prev_break = qsort_break_even;
-            qsort_break_even *= qsort_break_even;
-            if (qsort_break_even < prev_break) {
-               qsort_break_even = (part_right - part_left) + 1;
-            }
-#endif
-         } else {
-            qsort_break_even = QSORT_BREAK_EVEN;
-         }
-#endif
+		if (q == f1) {
+		    FROMTOUPTO(f2, tp2, t);
+		    *tp2++ = *f1++;
+		} else {
+		    FROMTOUPTO(f1, tp2, t);
+		    *tp2++ = *f2++;
+		}
+	    }
 
-         if (part_left < pc_left) {
-            /* There are elements on the left which need more processing.
-               Check the right as well before deciding what to do.
-            */
-            if (pc_right < part_right) {
-               /* We have two partitions to be sorted. Stack the biggest one
-                  and process the smallest one on the next iteration. This
-                  minimizes the stack height by insuring that any additional
-                  stack entries must come from the smallest partition which
-                  (because it is smallest) will have the fewest
-                  opportunities to generate additional stack entries.
-               */
-               if ((part_right - pc_right) > (pc_left - part_left)) {
-                  /* stack the right partition, process the left */
-                  partition_stack[next_stack_entry].left = pc_right + 1;
-                  partition_stack[next_stack_entry].right = part_right;
-#ifdef QSORT_ORDER_GUESS
-                  partition_stack[next_stack_entry].qsort_break_even = qsort_break_even;
-#endif
-                  part_right = pc_left - 1;
-               } else {
-                  /* stack the left partition, process the right */
-                  partition_stack[next_stack_entry].left = part_left;
-                  partition_stack[next_stack_entry].right = pc_left - 1;
-#ifdef QSORT_ORDER_GUESS
-                  partition_stack[next_stack_entry].qsort_break_even = qsort_break_even;
-#endif
-                  part_left = pc_right + 1;
-               }
-               qsort_assert(next_stack_entry < QSORT_MAX_STACK);
-               ++next_stack_entry;
-            } else {
-               /* The elements on the left are the only remaining elements
-                  that need sorting, arrange for them to be processed as the
-                  next partition.
-               */
-               part_right = pc_left - 1;
-            }
-         } else if (pc_right < part_right) {
-            /* There is only one chunk on the right to be sorted, make it
-               the new partition and loop back around.
-            */
-            part_left = pc_right + 1;
-         } else {
-            /* This whole partition wound up in the pivot chunk, so
-               we need to get a new partition off the stack.
-            */
-            if (next_stack_entry == 0) {
-               /* the stack is empty - we are done */
-               break;
-            }
-            --next_stack_entry;
-            part_left = partition_stack[next_stack_entry].left;
-            part_right = partition_stack[next_stack_entry].right;
-#ifdef QSORT_ORDER_GUESS
-            qsort_break_even = partition_stack[next_stack_entry].qsort_break_even;
-#endif
-         }
-      } else {
-         /* This partition is too small to fool with qsort complexity, just
-            do an ordinary insertion sort to minimize overhead.
-         */
-         int i;
-         /* Assume 1st element is in right place already, and start checking
-            at 2nd element to see where it should be inserted.
-         */
-         for (i = part_left + 1; i <= part_right; ++i) {
-            int j;
-            /* Scan (backwards - just in case 'i' is already in right place)
-               through the elements already sorted to see if the ith element
-               belongs ahead of one of them.
-            */
-            for (j = i - 1; j >= part_left; --j) {
-               if (qsort_cmp(i, j) >= 0) {
-                  /* i belongs right after j
-                  */
-                  break;
-               }
-            }
-            ++j;
-            if (j != i) {
-               /* Looks like we really need to move some things
-               */
-	       int k;
-	       temp = array[i];
-	       for (k = i - 1; k >= j; --k)
-		  array[k + 1] = array[k];
-               array[j] = temp;
-            }
-         }
-
-         /* That partition is now sorted, grab the next one, or get out
-            of the loop if there aren't any more.
-         */
-
-         if (next_stack_entry == 0) {
-            /* the stack is empty - we are done */
-            break;
-         }
-         --next_stack_entry;
-         part_left = partition_stack[next_stack_entry].left;
-         part_right = partition_stack[next_stack_entry].right;
-#ifdef QSORT_ORDER_GUESS
-         qsort_break_even = partition_stack[next_stack_entry].qsort_break_even;
-#endif
-      }
-   }
 
-   /* Believe it or not, the array is sorted at this point! */
+	    /* Run out remaining list */
+	    if (f1 == l1) {
+		   if (f2 < l2) FROMTOUPTO(f2, tp2, l2);
+	    } else              FROMTOUPTO(f1, tp2, l1);
+	    p1 = NEXT(p1) = POTHER(tp2, list2, list1);
+	}
+	t = list1;
+	list1 = list2;
+	list2 = t;
+	last = PINDEX(list2, nmemb);
+    }
+    if (base == list2) {
+	last = PINDEX(list1, nmemb);
+	FROMTOUPTO(list1, list2, last);
+    }
+    Safefree(aux);
+    return;
 }