#include <stdio.h>
#include <stdlib.h>
#include <math.h>

/****Copyright (c) 1997,1998 All rights reserved
 ****A. V. Gerbessiotis 
 ****Permission to use, copy, modify, and distribute this software,
 ****and to incorporate it, in whole or in part, into 
 ****other software,is hereby granted without fee, provided that
 ****  (1) the above copyright notice and this permission 
 ****      notice appear in all copies of the source code, and 
 ****      the above copyright notice appear in clearly visible 
 ****      form on all supporting documentation and distribution 
 ****      media, and
 ****     (2) any redistribution of the software, in original
 ****         or modified form, be without fee and subject to
 ****         these same conditions.
 ****   No guarantee, whatsoever, is offered that the code works as
 ****   advertised or is absent of any, even damaging,
 ****   side-effects. Use this code at your own personal risk.
 ****/
extern double log();
extern double floor();

/* Shell Sort? Written ages ago...I don't know if it works...*/

void shellg(char *keys, int n, int size, int (*compare) ())
{
	register int i,j,k,s,t,m;
	char	*x;
	int 	h[64];
	int *y;

	t = ((int) ( floor(log((double)n)/log(2.0))))-1;
	h[t]=1;
	for(i=t-1;i>=0;i--)
	{
		h[i] = 2 * h[i+1]+1;
	}

	x = (char *) malloc(size*sizeof(char));

	for(m=0;m<=t;m++)
	{
		k=h[m]; 
		for(i=k;i<n;i++)
		{
			memcpy(x,&keys[i*size],size);
			j=i-k;
			s=1;
			while ((j>=0) && (s==1))
			{
				if (compare(x,&keys[j*size]) < 0)
				{
				memcpy(&keys[(j+k)*size],&keys[j*size],size);
				j=j-k;
				}
				else
					s=0;
			}
			memcpy(&keys[(j+k)*size],x,size);
			
		}
	}

}
