# include <stdio.h>
#define debug 0

#define MaximumKey 017777777777
#define MaxKey 4590
#define MinKey 1
#define NoKey (-1)
#define M 10
#define D 4
#define Error printf("An error has been detected\n")
typedef int typekey;
typedef	struct	rec {
		typekey k;
		struct rec *next;
		} *list;
typekey LastRand;

list Last, r;
list sort();

	typekey rand()
	/*** simple minded random number generator ***/
	/*** it uses Xn+1 = 11*Xn mod 4591 (11 is a prim root in 4591) ***/
	{
	extern typekey LastRand;
		LastRand = 11*LastRand % 4591;
		if ( LastRand<=0 ) LastRand = 1;
		return(LastRand);
	};

	checkorder( t )
	list t;
	{
	list i;
	if ( debug ) {
		i = t;
		printf("checkorder ");
		while ( i != NULL ) {
			printf(", %d", i->k);
			i = i->next;
			};
		printf("\n");
		};
	while ( t!=NULL ) {
		if ( t->next != NULL )
			if ( t->k > t->next->k ) printf("t out of order\n");
		t = t->next;
		}
	};

	int hash( t )
	list t;
	{
	int sum;
	sum = 0;
	while ( t != NULL ) {
		sum += t->k * (t->k+1);
		t = t->next;
		};
	return( sum );
	};

	trysort()
	{
	int h;
		h = hash( r );
		r = sort( r, 1 );
		if ( hash(r) != h )
			printf("Bad hash value\n");
		checkorder( r );
	};

	topins( val )
	typekey val;
	{
	list i;
		i = (list)malloc(sizeof(struct rec));
		i->k = val;
		i->next = r;
		r = i;
	};

main()
{
int i, is;
if (debug) printf("try with a null table \n");
r = NULL;	trysort();

if (debug) printf("try with a one-element table \n");
topins(1);	trysort();

if (debug) printf("try with a two-element table \n");
topins(2);	trysort();
r = NULL;	topins(2);	topins(2);	trysort();
r = NULL;	topins(2);	topins(1);	trysort();

if (debug) printf("try with 10-element table \n");
r = NULL;	for (i=1; i<=10; i++) topins(i);	trysort();
r = NULL;	for (i=1; i<=10; i++) topins(4321);	trysort();
r = NULL;	for (i=1; i<=10; i++) topins(101-i*i);	trysort();
LastRand = 101;
for (is=1; is<=10; is++) {
	r = NULL;	for (i=1; i<=10; i++) topins(rand());
	trysort();
	}
exit( 0 );
}
	charac(i,k)
	int i,k;
	{int b;
	b = 100000;
	for (; i>0; i--)	b /= 10;
	return( (k%b) / (b/10) );
	};

	list sort( s, j )
	list s;
	int j;
	
	{
	int i;
	list head[M], t;
	struct rec aux;
	extern list Last;
	if (s==NULL)	return(s);
	if ( s->next == NULL )	{Last = s;	return(s);}
	if ( j>D )	{
		for (Last=s; Last->next!=NULL; Last = Last->next);
		return( s );
		}
	for (i=0; i<M; i++)	head[i] = NULL;
	/* Place records in buckets */
	while (s != NULL)	{
		i = charac( j, s->k );
		t = s;
		s = s->next;
		t->next = head[i];
		head[i] = t;
		}
	/* sort recursively */
	t = &aux;
	for (i=0; i<M; i++)	if (head[i]!=NULL)	{
		t->next = sort( head[i], j+1 );
		t = Last;
		}
	return(aux.next);
	}