#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <limits.h>
#define	TEN	10
/****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.
 ****/

extern clock_t clock();
void quick();
void quicker();
void mergerg();
void merger2g();

int compare(int *x,int *y)
{
	return(*x-*y);
}


int main(int argc,char *argv[])
{
	int i,j,n,runs;
	int *ptr1,*ptr2,*ptr3,*bptr1,*bptr2,*bptr3;
	clock_t t1,t0;
	size_t n_t;
   	double elapsed;

   n=100; runs=1;
   if ( argc == 1 )
   	{
	      printf("Usage: sort size runs \n");
	}
   else
	   {
		n = atoi(argv[1]);
		runs=atoi(argv[2]);
	   }

	ptr1= (int*) malloc(n*sizeof(int));
	ptr2= (int*) malloc(n*sizeof(int));
	bptr1= (int*) malloc(n*sizeof(int));
	bptr2= (int*) malloc(n*sizeof(int));

	n_t =  n;

	for(i=0;i<n_t;i++) {
		bptr1[i]=(int) (n_t*(random()/ ((double) INT_MAX)));
		bptr2[i]=(int) (n_t*(random()/ ((double) INT_MAX)));
	}

	qsort(bptr1,n_t,sizeof(int),compare);
	qsort(bptr2,n_t,sizeof(int),compare);

	for(i=0;i<n_t;i++) ptr1[i] = bptr1[i];
	for(i=0;i<n_t;i++) ptr2[i] = bptr2[i];
	for(i=0;i<TEN;i++) printf("%d ",ptr1[i]);
	printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr1[i]);
	printf("\n");
	for(i=0;i<TEN;i++) printf("%d ",ptr2[i]);
	printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr2[i]);
	printf("\n");

	elapsed=0.0;
        for(j=0;j<runs;j++) {
	for(i=0;i<n_t;i++) ptr1[i] = bptr1[i];
	for(i=0;i<n_t;i++) ptr2[i] = bptr2[i];
	t0=clock();
	mergerg(ptr1,ptr2,n_t,n_t,sizeof(int),compare);
	t1=clock();
	elapsed += ((double)(t1-t0))/((double)CLOCKS_PER_SEC);
	}

	for(i=0;i<TEN;i++) printf("%d ",ptr1[i]);
	printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr1[i]);
	printf("\n");
	for(i=0;i<TEN;i++) printf("%d ",ptr2[i]);
	printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr2[i]);
	printf("\n");
        printf("merge v1:Elapsed time is %10.8f\n",elapsed);

	for(i=0;i<n_t;i++) ptr1[i] = bptr1[i];
	for(i=0;i<n_t;i++) ptr2[i] = bptr2[i];

	for(i=0;i<TEN;i++) printf("%d ",ptr1[i]);
	printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr1[i]);
	printf("\n");
	for(i=0;i<TEN;i++) printf("%d ",ptr2[i]);
	printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr2[i]);
	printf("\n");

	elapsed=0.0;
        for(j=0;j<runs;j++) {
	for(i=0;i<n_t;i++) ptr1[i] = bptr1[i];
	for(i=0;i<n_t;i++) ptr2[i] = bptr2[i];
	t0=clock();
	merger2g(ptr1,ptr2,n_t,n_t,sizeof(int),compare);
	t1=clock();
	elapsed +=((double) (t1-t0))/((double)CLOCKS_PER_SEC);
	}

	for(i=0;i<TEN;i++) printf("%d ",ptr1[i]);
	printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr1[i]);
	printf("\n");
	for(i=0;i<TEN;i++) printf("%d ",ptr2[i]);
	printf("...");
	for(i=n_t-TEN;i<n_t;i++) printf("%d ",ptr2[i]);
	printf("\n");
        printf("mymerge:Elapsed time is %10.8f\n",elapsed);




}
