/* SHELL SORT SUBROUTINE: Not as fast as QuickSort (qsort),	 */
/* but takes no stack space since it does not use recursion. */
/* The calling sequence is the same as qsort.                */

/* Copyright 1986 John Navas II, All Rights Reserved.
SSORT is made available for personal, non-commercial use only.  You
are granted a limited license to use SSORT, and to copy it and
distribute it, provided that no fee is charged for such copying and
distribution, and that it is ONLY distributed in its original,
unmodified state. */

void ssort( adr, num, eln, cmp )		/* SHELL SORT */
char *adr;								/* address of data table */
unsigned int num;						/* number of entries */
unsigned int eln;						/* length of entry in bytes */
int (*cmp)();							/* comparison routine */
{
	char *ten = adr + num * eln;		/* address past table */
	unsigned int pas;					/* pass number bias */
	unsigned int bia;					/* pass memory bias */
	unsigned int dlt;					/* shell increment/decrement */
	register char *i, *j;				/* pointers */
	char *is, *js;						/* shell save pointers */
	char *c;							/* check for shell up */
	char dir;							/* direction of shell */

	for ( pas = num >> 1; pas; pas = ( pas + 1 ) / 3 ) {	/* passes */
		for ( c = ( j = ( i = adr ) + ( bia = pas * ( dlt = eln ) ) ),
				dir = 0; j < ten; i += dlt, j += dlt ) {
			if ( j >= c && (*cmp)( i, j ) > 0 ) {	/* need to move entry */
				unsigned int l;					/* length to swap */
				char *it = i, *jt = j;			/* save pointers */
				for ( l = eln; l; --l ) {		/* swap chars */
					char sav = *i;
					*i++ = *j; *j++ = sav;
					}
				i = it; j = jt;					/* restore pointers */
				if ( ! dir ) {			/* if not yet going up */
					dir = 1;			/* then go up */
					is = i; js = j;		/* save pointers for shell up */
					dlt = - bia;		/* up increment */
					}
				continue;
				}
			if ( dir ) {				/* if going up */
				dir = 0;				/* go on down */
				i = is; j = js;			/* restore shell up pointers */
				dlt = eln;				/* restore up delta */
				}
			}
		}
	}
