## Merge sort

 # include #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; ik ); t = s; s = s->next; t->next = head[i]; head[i] = t; } /* sort recursively */ t = &aux; for (i=0; inext = sort( head[i], j+1 ); t = Last; } return(aux.next); }