/****Copyright (c) 1997-2009 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"

void g66non2(void *akeys, int n, int size, int (*compare) (const void*,const void*))
{
 register int i,j,l,r,s,M,c;
 register char *keys;
 register char *SRC,*DES;
 char Split[MAX_KEY_SIZE],Tmp[MAX_KEY_SIZE];
 register char *split,*tmp,*pi,*pj;
 static int	lstack[STACK_SIZE_QS];
 static int	rstack[STACK_SIZE_QS];

  if (n <= 1) return;
  keys  = (char *) akeys;
#ifdef SANITY_CHECK
/*
  tmp   = (char *) malloc(size*sizeof(char));
  split = (char *) malloc(size*sizeof(char));
*/
  check_if_null(tmp,  "g66non2","tmp");
  check_if_null(split,"g66non2","split");
#endif
  split=Split;tmp=Tmp;
  s=0;
  lstack[0]=0;rstack[0]=n-1;
do {
    l=lstack[s]; r=rstack[s]; s--;
    do {
	i=l; 
	j=r; 
	MEMCPY(split,&keys[((l+r)>>1)*size],size);
        pi=&keys[i*size];
        pj=&keys[j*size];
	do {
          while (compare(pi,split) < 0) {i++;pi+=size;}
          while (compare(split,pj) < 0) {j--;pj-=size;}

	  if (i <= j ) {
/*
            MEMCPY(tmp,pi,size);
            MEMCPY(pi,pj,size);
            MEMCPY(pj,tmp,size);
*/
            M=size;
            do {
             c= *pi; *pi++ = *pj ; *pj++=c;
            } while (--M);
            i++; pj -=size;
            j--; pj -=size;
           }
	} while (i <= j); 
		
	if (i < r) {
          if ((r-i) <THRES16 )
	    BASES (pi,(r-i+1),size,compare);
          else {
	    s++; lstack[s]=i; rstack[s]=r;
          }
        }
	r=j;
      } while ( l < r);

   } while (s>= 0);
/*
 free((void *)split); free((void *)tmp);
*/
}
