/****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 g65non3(void *akeys, int n, int size, int (*compare) (const void*,const void*))
{
 register int i,j,l,r,s,M;
 register char	*split,*tmp, *keys,*SRC,*DES;
 register char *pi,*pj;
 static int	lstack[STACK_SIZE_QS];
 static int	rstack[STACK_SIZE_QS];

  if (n <= 1) return;
  keys  = (char *) akeys;
  tmp   = (char *) malloc(size*sizeof(char));
  split = (char *) malloc(size*sizeof(char));
#ifdef SANITY_CHECK
  check_if_null(tmp,  "g65non3","tmp");
  check_if_null(split,"g65non3","split");
#endif
  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);
            i++; pi +=size;
            j--; pj -=size;
           }
	} while (i <= j); 
		
        if ((j-l) <(r-i)) {
	  if (i < r) {
             if ((r-i+1) <THRES16 )
	         BASES (pi,(r-i+1),size,compare);
             else {
	          s++; lstack[s]=i; rstack[s]=r;
             }
          }
 	  r=j;
        }
        else {
          if (l<j) {
             if ((j-l+1) <THRES16 )
	         BASES (pi,(j-l+1),size,compare);
             else {
	          s++; lstack[s]=l; rstack[s]=j;
             }
          }
          l=i;
        }
      } while ( l < r);

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