foundationI_fluffos_v1/
foundationI_fluffos_v1/bin/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/ChangeLog.old/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/Win32/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/compat/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/compat/simuls/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/include/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/testsuite/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/testsuite/clone/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/testsuite/command/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/testsuite/data/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/testsuite/etc/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/testsuite/include/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/testsuite/inherit/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/testsuite/inherit/master/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/testsuite/log/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/testsuite/single/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/testsuite/single/tests/compiler/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/testsuite/single/tests/efuns/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/testsuite/single/tests/operators/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/testsuite/u/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/tmp/
foundationI_fluffos_v1/fluffos-2.9-ds2.12/windows/
foundationI_fluffos_v1/lib/
foundationI_fluffos_v1/lib/cmds/ambassador/
foundationI_fluffos_v1/lib/cmds/database/
foundationI_fluffos_v1/lib/cmds/soul/
foundationI_fluffos_v1/lib/daemon/include/
foundationI_fluffos_v1/lib/daemon/save/
foundationI_fluffos_v1/lib/daemon/services/
foundationI_fluffos_v1/lib/daemon/soul/
foundationI_fluffos_v1/lib/doc/build/
foundationI_fluffos_v1/lib/doc/build/room/
foundationI_fluffos_v1/lib/doc/build/virtual/
foundationI_fluffos_v1/lib/doc/driver/
foundationI_fluffos_v1/lib/doc/efun/
foundationI_fluffos_v1/lib/doc/etc/
foundationI_fluffos_v1/lib/doc/help/creator/
foundationI_fluffos_v1/lib/doc/help/hm/
foundationI_fluffos_v1/lib/doc/help/user/
foundationI_fluffos_v1/lib/doc/lpc/basic/
foundationI_fluffos_v1/lib/doc/lpc/data_types/
foundationI_fluffos_v1/lib/doc/lpc/etc/
foundationI_fluffos_v1/lib/doc/lpc/intermediate/
foundationI_fluffos_v1/lib/doc/lpc/types/
foundationI_fluffos_v1/lib/doc/mudlib/
foundationI_fluffos_v1/lib/doc/mudlib/features/
foundationI_fluffos_v1/lib/domains/Examples/etc/
foundationI_fluffos_v1/lib/domains/Examples/room/
foundationI_fluffos_v1/lib/domains/Examples/virtual/
foundationI_fluffos_v1/lib/domains/Examples/virtual/exaA/
foundationI_fluffos_v1/lib/domains/Examples/virtual/exaB/
foundationI_fluffos_v1/lib/domains/Examples/weapon/
foundationI_fluffos_v1/lib/domains/Standard/
foundationI_fluffos_v1/lib/domains/Standard/pools/
foundationI_fluffos_v1/lib/domains/Standard/std/
foundationI_fluffos_v1/lib/domains/Standard/xtra/
foundationI_fluffos_v1/lib/include/
foundationI_fluffos_v1/lib/news/
foundationI_fluffos_v1/lib/secure/cfg/
foundationI_fluffos_v1/lib/secure/cmds/adm/
foundationI_fluffos_v1/lib/secure/cmds/ambassador/
foundationI_fluffos_v1/lib/secure/cmds/mortal/
foundationI_fluffos_v1/lib/secure/etc/
foundationI_fluffos_v1/lib/secure/etc/approval/
foundationI_fluffos_v1/lib/secure/etc/elections/
foundationI_fluffos_v1/lib/secure/etc/mudlib/
foundationI_fluffos_v1/lib/secure/etc/quests/
foundationI_fluffos_v1/lib/secure/save/daemon/
foundationI_fluffos_v1/lib/secure/save/postal/d/descartes/
foundationI_fluffos_v1/lib/secure/save/users/d/
foundationI_fluffos_v1/lib/secure/std/
foundationI_fluffos_v1/lib/std/obj/
foundationI_fluffos_v1/lib/std/room/
foundationI_fluffos_v1/lib/std/user/
foundationI_fluffos_v1/lib/std/virtual/
foundationI_fluffos_v1/old/
foundationI_fluffos_v1/win32/
/* median-3 variant of quicksort - coded by John Garnett.

   using this quicksort rather than the builtin one because most
   builtin implementations choke on non-deterministic compare functions
   (and we can't control what compare function is used since it is at
   the mudlib level).  Based on algorithm appearing in _Data Structures and
   Algorithm Analysis_ by Cawnthorpe.
*/

#include "std.h"
#include "qsort.h"

#define LEN sizeof(svalue_t)
#define MAX_LEN 1000

INLINE_STATIC void doSwap (char *, char *, int);
static void qSort (void *, int, int, int, int, int (*) ());

INLINE_STATIC void doSwap (register char * one, register char * two,
                             register int size)
{
    register char t;

    while (size--) {
	t = *one;
	*(one++) = *two;
	*(two++) = t;
    }
}

/* qsort adapted from page 87 of K&R 2nd edition */

static void qSort(void *v, int left, int right, int size, int rightmost, int (*compar) (void *, void *))
{
    int i, last, szleft;

    if ((left >= right) || (left < 0) || (right > rightmost) || (right < 0)) {
	return;
    }
    szleft = size * left;
    doSwap((char *) v + szleft, (char *) v + (size * ((left + right) / 2)), size);
    last = left;
    for (i = left + 1; i <= right; i++) {
	if ((*compar) ((char *) v + (size * i), (char *) v + szleft) < 0) {
	    doSwap((char *) v + (size * ++last), (char *) v + (size * i), size);
	}
    }
    doSwap((char *) v + szleft, (char *) v + (size * last), size);
    qSort(v, left, last - 1, size, rightmost, compar);
    qSort(v, last + 1, right, size, rightmost, compar);
}

void quickSort(void *a, int nmemb, int size, int (*compar) (void *, void *))
{
    if (nmemb < 2) {
	return;
    }
    qSort(a, 0, nmemb - 1, size, nmemb - 1, compar);
}