/****Copyright (c) 1997-2005 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.
 ****/
#include "ssrt.h"
#include "math.h"

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

void g28shell
(void *akeys,int n,int size,int (*compare)(const void*,const void*))
{
 register int i,j,k,s,t,m,M;
 register char	*tmp,*keys,*SRC,*DES;
 int 	h[64];

 if (n<=1) return;
 keys = (char *)akeys;
 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;
 }
 tmp = (char *) malloc(size*sizeof(char));
#ifdef SANITY_CHECK
  check_if_null(tmp,"g28shell","tmp");
#endif
 for(m=0;m<=t;m++) {
   k=h[m]; 
   for(i=k;i<n;i++) {
      MEMCPY(tmp,&keys[i*size],size);
      j=i-k;
      s=1;
      while ((j>=0) && (s==1)) {
        if (compare(tmp,&keys[j*size]) < 0) {
          MEMCPY(&keys[(j+k)*size],&keys[j*size],size);
          j=j-k;
        }
        else
          s=0;
      }
      MEMCPY(&keys[(j+k)*size],tmp,size);
    }
  }
}
