#include <sys/time.h>
#include "merge_sort.h"
#include "crearreglo.h"

/*funcion merge*/

void merge(int *A,int n,int m)
{
int i,j,k;
int *aux;
aux=(int*)malloc(n*sizeof(int));  	
for (i=0;i<n;i++) *(aux+i) = *(A+i);
for (i=0,j=0,k=m;i<n;i++)
	{
	if((aux[j]<aux[k])&&(j<m)||(k>=n)){A[i]= aux[j];j++;} 
	else
	{A[i]=aux[k];k++;}
	}
}

/*funcion mergesort*/
void mergesort_1(int *A,int n)
{
int m=n/2;
if(n<=1) return;
mergesort_1(A,m);
mergesort_1(A+m,n-m);
merge(A,n,m);
}

/*rutina para medicion de tiempo de mergesort, entrega el resultado en [useg]
del tipo long*/

long mergesort(int *A,int n)
{
struct timeval q,r;
gettimeofday(&q,0);
mergesort_1(A,n);
gettimeofday(&r,0);
return((r.tv_sec*1000000+r.tv_usec)-(q.tv_sec*1000000+q.tv_usec));
}

/*algoritmo mergesort que llama a funcion copiarreglo en el 75% del tiempo
de ejecucion aproximadamente*/

void mergesort_2(int *parcial,int *final,int SIZE,int *A,int n)
{
int m = n/2;
if (n<=1) return;
mergesort_2(parcial,final,SIZE,A,m);
if(m==SIZE/4) copiarreglo(parcial,final,SIZE);
mergesort_2(parcial,final,SIZE,A+m,n-m);
merge(A,n,m);
}