/****Copyright (c) 1997-2008 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 <memory.h>
#include <limits.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>

typedef int    data;
#define PRINT_INT 1
#define Times2(x)            ((x) << 1)


/* Date: Jun 23, 2005 */
#ifndef TRUE
#define TRUE            1
#endif
#ifndef FALSE
#define	FALSE		0
#endif
#ifndef MIN
#define	MIN(x,y)	((x)<=(y)?(x):(y)) 
#endif
#ifndef MAX
#define	MAX(x,y)	((x)>=(y)?(x):(y))
#endif
#ifndef CEIL
#define CEIL(X,Y)       ((X != 0)?(1+ (X-1)/Y):0)  
#endif
#ifndef FLOOR
#define FLOOR(X,Y)      (X/Y)  
#endif

#define check_if_null(X,Y,Z)  avg_checknull(X,Y,Z);

#define GRANDOM(X)  (int)((random()/((double)2147483647.0))*X)
#define GSRANDOM()   srandom((unsigned int)time(NULL))
#define STACK_SIZE_QS 64
#define MAX_KEY_SIZE  64   /* in bytes*/
#define THRES16    8   /*  NEW: 24 or 16 but for dsort use 8 */
                     /*   OLD: 16 or 24: 48,g21ins for PIV/III Linux , 8-16 for SUNS for MERGE */
#define TMERGE   16  /* Threshold for MERGE SORT; 16 or 8 might better than  24 */
#define THRESI16 24  /* 20 for non1 24 for other */
#define TMERGEI  8   /* THRESHOLD FOR MERGESORT 8 -64 ok */
#define BASES   g21ins
#define BASEI   i01ins /* Function For Base Sorting in Integer Quick Sort */
#define FIRST_KEY  0
#define MIDDLE_KEY 1
#define RANDOM_KEY 2
#define SPLITTER  MIDDLE_KEY
#undef ALTERNATIVE

void g01ins  (void *,int ,int ,int (*)(const void*,const void*));
void g02ins  (void *,int ,int ,int (*)(const void*,const void*));
void g04sel  (void *,int ,int ,int (*)(const void*,const void*));
void g05bub  (void *,int ,int ,int (*)(const void*,const void*));
void g06bins (void *,int ,int ,int (*)(const void*,const void*));
void g07shake(void *,int ,int ,int (*)(const void*,const void*));
void g08shell(void *,int ,int ,int (*)(const void*,const void*));
void g09shlln(void *,int ,int ,int (*)(const void*,const void*));
void g11ins  (void *,int ,int ,int (*)(const void*,const void*));
void g12ins  (void *,int ,int ,int (*)(const void*,const void*));
void g14sel  (void *,int ,int ,int (*)(const void*,const void*));
void g21ins  (void *,int ,int ,int (*)(const void*,const void*));
void g24sel  (void *,int ,int ,int (*)(const void*,const void*));
void g25bub  (void *,int ,int ,int (*)(const void*,const void*));
void g26bins (void *,int ,int ,int (*)(const void*,const void*));
void g27shake(void *,int ,int ,int (*)(const void*,const void*));
void g28shell(void *,int ,int ,int (*)(const void*,const void*));
void g20mrgit(void *,int ,int ,int (*)(const void*,const void*));
void g77shake(void *,int ,int ,int (*)(const void*,const void*));
void g78shell(void *,int ,int ,int (*)(const void*,const void*));

void g30mrgit(void *,int ,int ,int (*)(const void*,const void*));
void g39mrgit(void *,int ,int ,int (*)(const void*,const void*));
void g31mrgnn(void *,int ,int ,int (*)(const void*,const void*));
void g33heapx(void *,int ,int ,int (*)(const void*,const void*));
void g34heapx(void *,int ,int ,int (*)(const void*,const void*));
void g35heapn(void *,int ,int ,int (*)(const void*,const void*));
void g35heapx(void *,int ,int ,int (*)(const void*,const void*));
void g36heapn(void *,int ,int ,int (*)(const void*,const void*));
void g36heapx(void *,int ,int ,int (*)(const void*,const void*));
void g37heapx(void *,int ,int ,int (*)(const void*,const void*));

void g50gnu  (void *,int ,int ,int (*)(const void*,const void*));
void g51wbh  (void *,int ,int ,int (*)(const void*,const void*));
void g52dbh  (void *,int ,int ,int (*)(const void*,const void*));
void g53fbc  (void *,int ,int ,int (*)(const void*,const void*));
void g153fbc  (void *,int ,int ,int (*)(const void*,const void*));
void g154fbc  (void *,int ,int ,int (*)(const void*,const void*));
void g253fbc  (void *,int ,int ,int (*)(const void*,const void*));
void g55non1 (void *,int ,int ,int (*)(const void*,const void*));

void g61wbh  (void *,int ,int ,int (*)(const void*,const void*));
void g161wbh  (void *,int ,int ,int (*)(const void*,const void*));
void g62dbh  (void *,int ,int ,int (*)(const void*,const void*));
void g162dbh  (void *,int ,int ,int (*)(const void*,const void*));
void g63fbc  (void *,int ,int ,int (*)(const void*,const void*));
void g65non1 (void *,int ,int ,int (*)(const void*,const void*));
void g65non2 (void *,int ,int ,int (*)(const void*,const void*));
void g65non3 (void *,int ,int ,int (*)(const void*,const void*));
void g66non1 (void *,int ,int ,int (*)(const void*,const void*));
void g66non2 (void *,int ,int ,int (*)(const void*,const void*));
void g266non2(void *,int ,int ,int (*)(const void*,const void*));
void g67     (void *,int ,int ,int (*)(const void*,const void*));
void g68non1 (void *,int ,int ,int (*)(const void*,const void*));
void g168non1 (void *,int ,int ,int (*)(const void*,const void*));
void g68non2 (void *,int ,int ,int (*)(const void*,const void*));
void g68wbh  (void *,int ,int ,int (*)(const void*,const void*));
void g168wbh (void *,int ,int ,int (*)(const void*,const void*));
void g268wbh (void *,int ,int ,int (*)(const void*,const void*));
void g69non1 (void *,int ,int ,int (*)(const void*,const void*));
void my1     (void *,int ,int ,int (*)(const void*,const void*));
void my2     (void *,int ,int ,int (*)(const void*,const void*));
void my3     (void *,int ,int ,int (*)(const void*,const void*));
void my4     (void *,int ,int ,int (*)(const void*,const void*));
void my5     (void *,int ,int ,int (*)(const void*,const void*));
void g170my3     (void *,int ,int ,int (*)(const void*,const void*));
void g170my4     (void *,int ,int ,int (*)(const void*,const void*));
void g170my5     (void *,int ,int ,int (*)(const void*,const void*));

void i01ins  (        data *, int); 
void i30mrgit(        data *, int); 

void i32rdx2 (unsigned int *, int);
void i32rdx4 (unsigned int *, int);
void i32rdx  (unsigned int *, int); 

void i33heapx(        data *, int); 
void i34heapx(        data *, int); 
void i35heapn(        data *, int); 
void i35heapx(        data *, int); 
void i36heapn(        data *, int); 
void i36heapx(        data *, int); 

void i50gnu  (void *,int ,int ,int (*)(const void*,const void*));

void i51wbh (        data *, int); 
void i52dbh (        data *, int); 
void i55non0(        data *, int); 
void i55non1(        data *, int); 
void i63fbc (        data *, int); 

#define SWAPP(i1,i2) \
  {ii = size;do {k = *(i1);*(i1)++ = *(i2);*(i2)++ = k;} while(--ii);}
#define SWAPPY(XX,YY,TT,SS) {DES=(XX);SRC=(YY);M=(SS); do {*TT=*DES;*DES++=*SRC;*SRC++=*TT;} while ( --M); }

#define MEMCPY(X,Y,SIZE)  memcpy((X),(Y),(SIZE))
#undef MEMCPY
#define MEMCPY(XX,YY,SS) {DES=(XX);SRC=(YY);M=(SS); do {*DES++=*SRC++;} while (--M); }
#define IMEMCPY(XX,YY,SS) {DES=(XX);SRC=(YY);M=(SS); do {*DES++=*SRC++;} while (--M); }
