#include <stdio.h>
#include <stdlib.h>


#define INFINITY 2.0

#include "merge_sort.h"

int merge(double *A, int p, int q, int r);
double rand_unif();


double rand_unif() 
{
    return (1.0 * random()) / RAND_MAX;
}


int merge(double *A, int p, int q, int r)
{
    int count = 0, i, j, k, n1 = q - p + 1, n2 = r - q;
    double *L, *R;
    L = (double*) malloc((n1+1) * sizeof(double));
    R = (double*) malloc((n2+1) * sizeof(double));
    for (i = 0; i < n1; i++) L[i] = A[p + i];
    for (j = 0; j < n2; j++) R[j] = A[q + j + 1];
    L[n1] = R[n2] = INFINITY;
    i = 0;
    j = 0;
    for (k = p; k <= r; k++) {
	count++;
	if (L[i] <= R[j]) {
	    A[k] = L[i];
	    i++;
	}
	else {
	    A[k] = R[j];
	    j++;
	}
    }
    free(L);
    free(R);
    return count;
}

int merge_sort(double *A, int p, int r)
{
    int q, count = 0;
    if (p < r) {
	q = (p + r) / 2;
	count += merge_sort(A, p, q);
	count += merge_sort(A, q+1, r);
	count += merge(A, p, q, r);
    }
    return count;
}

int merge_sort_random(double *A, int n) 
{
    int i;
    for (i = 0; i < n; i++) A[i] = rand_unif();
    return merge_sort(A, 0, n-1);
}