/****Copyright (c) 1997 All rights reserved
 **** C. J. Siniolakis
 ****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 <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
#include <memory.h>
#include <limits.h>
#define Div2(x)               ((x) >> 1)
#define Times2(x)             ((x) << 1)
#define CDiv(x, y)            (((x) != 0) ? ((((x) - 1)/(y)) + 1) : 0)
#define Mask(x, sbit, nbits)  ((x >> sbit) & ~(UINT_MAX << nbits))
#define MIN(X,Y)              ((X)<(Y)?(X):(Y))

int FLog2 (int x)
{
  register int l ;

  if (x <= 1) return(0);
  else
    {
      l = 0 ;
      while (x = Div2(x)) ++l ;
      return(l);
    }
}

int CLog2 (int x)
{
  register int l ;

  if (x <= 1) return(0);
  else
    {
      --x ; l = 1 ;
      while (x = Div2(x)) ++l ;
      return(l);
    }
}

int Exp2 (int x)
{
  return (int)((unsigned int)(1) << x) ;
}


void sort_ins(char *src, int n,int sbytes,int (*compare)() )
{
  char   *tmp ;
  register int     i, idx ;

  if ((n <= 1)  || (sbytes <= 0)) return ;

  tmp= (char *) malloc(sbytes*sizeof(char));
  if (tmp == NULL) {
		printf("error: malloc\n");
		exit(123);
	}


  for (i = 1 ; i < n ; ++i) {
      memcpy(tmp, &src[i*sbytes], sbytes) ;
      idx = i ;
      while ((idx > 0) && compare(&src[(idx-1)*sbytes], tmp) > 0) {
          memcpy(&src[idx*sbytes], &src[(idx-1)*sbytes], sbytes) ;
          --idx ;
        }
      memcpy(&src[idx*sbytes], tmp, sbytes) ;
    }
 
  free(tmp) ;
}

void qs (char *src, int   n,int size,int (*compare)())
{
  char *mid,*tmp;
  register int  l, r ;

  mid = (char *) malloc(size*sizeof(char));
  tmp = (char *) malloc(size*sizeof(char));
  if (n <= 1) return ;
  l=0;r=n-1;

  memcpy(mid,&src[0],size);

  while (l <= r)
    {
      while (compare(&src[l*size],mid)<0) ++l ;
      while (compare(mid,&src[r*size])<0) --r ;
      if (l <= r)
        {
	  memcpy(tmp,&src[l*size],size);
	  memcpy(&src[l*size],&src[r*size],size);
	  memcpy(&src[r*size],tmp,size);
          ++l ; --r ;
        }
    }
  
  if (r > 0) 
    {
      if ((r + 1) < 16) sort_ins(src, r + 1,size,compare) ;
      else qs(src, r + 1,size,compare) ;
    }
  if (l < n) 
    {
      if ((n - l) < 16) sort_ins(&src[l*size], n - l,size,compare) ;
      else qs(&src[l*size], n - l,size,compare) ;
    }
}
           
void quick3g(char *keys, int n, int size, int (*compare) ())
{
  if (n <= 1) return ;
  qs(keys,n,size,compare);
}

void sort_mrg ( char    *src, int   n, int   sbytes, int    (*compare)() )
{
  char   *temp ;
  char   *tmp, *s, *t ;
  register int   phase ;
  register int idx;
  register int  i, j, l ;
  int  q, r ;


  if ((n <= 1)  || (sbytes <= 0)) return ;

  temp= (char *) malloc(n*sbytes*sizeof(char));
  if (temp == NULL) {
		printf("error: malloc\n");
		exit(123);
	}

  for (idx = 0 ; idx < n ; idx += 16    )
    {
      sort_ins(&src[idx*sbytes], MIN(16    , (n - idx)), sbytes, compare) ;
    }

  s = src ; t = temp ;
  for (phase = 16     ; phase < n ; phase = Times2(phase))
    { 
      for (idx = 0 ; idx < n ; idx += Times2(phase))
        {
          q = MIN(idx + Times2(phase), n) ; r = MIN(idx + phase, n) ;
          i = r ; j = idx ; l = idx ;  
          while ((i < q) && (j < r))
            {
              if (compare(&s[i*sbytes], &s[j*sbytes]) < 0)
                {
                  memcpy(&t[l*sbytes], &s[i*sbytes], sbytes) ;
                  ++i ; ++l ; 
                }
              else
                {
                  memcpy(&t[l*sbytes], &s[j*sbytes], sbytes) ;
                  ++j ; ++l ;
                }
             }

           if (i < q) memcpy(&t[l*sbytes], &s[i*sbytes], (q - i) * sbytes) ;    
           if (j < r) memcpy(&t[l*sbytes], &s[j*sbytes], (r - j) * sbytes) ;
        }
 
      tmp = s ; s = t ; t = tmp ;
    }

  if (s != src) memcpy(src, s, n * sbytes) ; 

  free(temp);
}
