dsIIr4/bin/
dsIIr4/extra/creremote/
dsIIr4/extra/wolfpaw/
dsIIr4/lib/cmds/admins/
dsIIr4/lib/cmds/common/
dsIIr4/lib/cmds/creators/include/
dsIIr4/lib/cmds/creators/include/SCCS/
dsIIr4/lib/daemon/services/
dsIIr4/lib/doc/
dsIIr4/lib/domains/Ylsrim/
dsIIr4/lib/domains/Ylsrim/adm/
dsIIr4/lib/domains/Ylsrim/armor/
dsIIr4/lib/domains/Ylsrim/broken/
dsIIr4/lib/domains/Ylsrim/fish/
dsIIr4/lib/domains/Ylsrim/meal/
dsIIr4/lib/domains/Ylsrim/npc/
dsIIr4/lib/domains/Ylsrim/virtual/
dsIIr4/lib/domains/Ylsrim/weapon/
dsIIr4/lib/domains/campus/adm/
dsIIr4/lib/domains/campus/etc/
dsIIr4/lib/domains/campus/meals/
dsIIr4/lib/domains/campus/npc/
dsIIr4/lib/domains/campus/save/
dsIIr4/lib/domains/campus/txt/
dsIIr4/lib/domains/campus/txt/ai/charles/
dsIIr4/lib/domains/campus/txt/ai/charles/bak2/
dsIIr4/lib/domains/campus/txt/ai/charles/bak2/bak1/
dsIIr4/lib/domains/campus/txt/ai/charly/
dsIIr4/lib/domains/campus/txt/ai/charly/bak/
dsIIr4/lib/domains/campus/txt/jenny/
dsIIr4/lib/domains/default/creator/
dsIIr4/lib/domains/default/doors/
dsIIr4/lib/domains/default/etc/
dsIIr4/lib/domains/default/virtual/
dsIIr4/lib/domains/default/weap/
dsIIr4/lib/domains/town/virtual/
dsIIr4/lib/lib/comp/
dsIIr4/lib/lib/lvs/
dsIIr4/lib/lib/user/
dsIIr4/lib/lib/virtual/
dsIIr4/lib/log/
dsIIr4/lib/obj/book_source/
dsIIr4/lib/obj/include/
dsIIr4/lib/realms/template/
dsIIr4/lib/realms/template/adm/
dsIIr4/lib/realms/template/area/armor/
dsIIr4/lib/realms/template/area/npc/
dsIIr4/lib/realms/template/area/obj/
dsIIr4/lib/realms/template/area/room/
dsIIr4/lib/realms/template/area/weap/
dsIIr4/lib/realms/template/bak/
dsIIr4/lib/realms/template/cmds/
dsIIr4/lib/save/
dsIIr4/lib/save/kills/o/
dsIIr4/lib/secure/cfg/classes/
dsIIr4/lib/secure/cmds/creators/include/
dsIIr4/lib/secure/cmds/players/
dsIIr4/lib/secure/cmds/players/include/
dsIIr4/lib/secure/daemon/include/
dsIIr4/lib/secure/lib/
dsIIr4/lib/secure/lib/include/
dsIIr4/lib/secure/lib/net/include/
dsIIr4/lib/secure/lib/std/
dsIIr4/lib/secure/modules/
dsIIr4/lib/secure/npc/
dsIIr4/lib/secure/obj/include/
dsIIr4/lib/secure/room/
dsIIr4/lib/secure/save/
dsIIr4/lib/secure/save/boards/
dsIIr4/lib/secure/save/players/g/
dsIIr4/lib/secure/tmp/
dsIIr4/lib/secure/verbs/creators/
dsIIr4/lib/shadows/
dsIIr4/lib/spells/
dsIIr4/lib/std/board/
dsIIr4/lib/std/lib/
dsIIr4/lib/tmp/
dsIIr4/lib/verbs/admins/include/
dsIIr4/lib/verbs/common/
dsIIr4/lib/verbs/common/include/
dsIIr4/lib/verbs/creators/include/
dsIIr4/lib/verbs/players/include/SCCS/
dsIIr4/lib/verbs/rooms/
dsIIr4/lib/verbs/rooms/include/
dsIIr4/lib/www/
dsIIr4/v22.2b14-dsouls2/
dsIIr4/v22.2b14-dsouls2/ChangeLog.old/
dsIIr4/v22.2b14-dsouls2/Win32/
dsIIr4/v22.2b14-dsouls2/compat/
dsIIr4/v22.2b14-dsouls2/compat/simuls/
dsIIr4/v22.2b14-dsouls2/include/
dsIIr4/v22.2b14-dsouls2/mudlib/
dsIIr4/v22.2b14-dsouls2/testsuite/
dsIIr4/v22.2b14-dsouls2/testsuite/clone/
dsIIr4/v22.2b14-dsouls2/testsuite/command/
dsIIr4/v22.2b14-dsouls2/testsuite/data/
dsIIr4/v22.2b14-dsouls2/testsuite/etc/
dsIIr4/v22.2b14-dsouls2/testsuite/include/
dsIIr4/v22.2b14-dsouls2/testsuite/inherit/
dsIIr4/v22.2b14-dsouls2/testsuite/inherit/master/
dsIIr4/v22.2b14-dsouls2/testsuite/log/
dsIIr4/v22.2b14-dsouls2/testsuite/single/
dsIIr4/v22.2b14-dsouls2/testsuite/single/tests/compiler/
dsIIr4/v22.2b14-dsouls2/testsuite/single/tests/efuns/
dsIIr4/v22.2b14-dsouls2/testsuite/single/tests/operators/
dsIIr4/v22.2b14-dsouls2/testsuite/u/
dsIIr4/v22.2b14-dsouls2/tmp/
dsIIr4/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 PROT((char *, char *, int));
static void qSort PROT((void *, int, int, int, int, int (*) ()));

INLINE_STATIC void doSwap P3(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(v, left, right, size, rightmost, compar)
    void *v;
    int left, right, size, rightmost;
    int (*compar) PROT((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(a, nmemb, size, compar)
    void *a;
    int nmemb, size;
    int (*compar) PROT((void *, void *));
{
    if (nmemb < 2) {
	return;
    }
    qSort(a, 0, nmemb - 1, size, nmemb - 1, compar);
}