#include <stdio.h>
#include <stdlib.h>
#include <math.h>
/****Copyright (c) 1997,1998,1999-2002 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.
 ****/

void mergeg(char *keys, int n, int size, int (*compare) ())
{
	register int i;
	int j,k,l,t;
	int h,m,q,p,r,up;
	int *x;
	char *y;

	up=1;p=1;
	y = (char*) malloc(2*n*size);
	for(i=0;i<n;i++)
		memcpy(&y[i*size],&keys[i*size],size);


do {
	h=1; m=n;
	if (up==1) {
		i=0;j=n-1;k=n;l=2*n-1;
	}
	else {
		k=0;l=n-1;i=n;j=2*n-1;
	}

do {
	if (m >= p) 
		q=p;
	else 
		q=m;
	m=m-q;

	if (m >= p)
		r=p;
	else
		r=m;
	m=m-r;


	while ((q != 0) && ( r != 0)) {
		if (compare(&y[i*size],&y[j*size]) < 0) {
			memcpy(&y[k*size],&y[i*size],size);
			k +=h; i++; q--;
		}
		else {
			memcpy(&y[k*size],&y[j*size],size);
			k +=h; j--; r--;
		}
	}

		
	while ( r != 0) {
		memcpy(&y[k*size],&y[j*size],size);
		k +=h; j--; r--;
	}
	
	while ( q != 0) {
		memcpy(&y[k*size],&y[i*size],size);
		k +=h; i++; q--;
	}
	h=-h; t=k; k=l; l=t;
} while (m>0);
	up=1-up; p=2*p;
} while (p < n);
/*
	if (up==0)
		for(i=0;i<n;i++)
			memcpy(&y[i*size],&y[(i+n)*size],size);
	for(i=0;i<n;i++)
		memcpy(&keys[i*size],&y[i*size],size);
*/
/*
	if (up==0)
		for(i=0;i<n;i++)
			memcpy(&keys[i*size],&y[(i+n)*size],size);
	else
		for(i=0;i<n;i++)
			memcpy(&keys[i*size],&y[i*size],size);
*/
	if (up==0)
			memcpy(&keys[0*size],&y[(n)*size],n*size);
	else
			memcpy(&keys[0*size],&y[0*size],n*size);
}
