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

void merge(double *A, int p, int q, int r);
void merge_sort(double *A, int p, int r);
double elapsed_time(struct timespec start, struct timespec end);
double time_test(int n);



main() 
{
    int i;
    srandom(time(NULL));
    for (i = 500000; i < 10000000; i += 500000) {
	printf("%d %f\n", i, time_test(i));
    }
    return 0;
}


double elapsed_time(struct timespec start, struct timespec end)
{
    return ((double) end.tv_sec - start.tv_sec) + ((double) end.tv_nsec - start.tv_nsec) / 1e9;
}


double time_test(int n)
{
    int i;
    struct timespec start_time, end_time;
    double *x = (double *) malloc(n * sizeof(double));
    for (i = 0; i < n; i++) { 
	x[i] = 1.0 * random() / RAND_MAX; 
    }
    clock_gettime(CLOCK_MONOTONIC, &start_time);
    merge_sort(x, 0, n-1);
    clock_gettime(CLOCK_MONOTONIC, &end_time);
    free(x);
    return elapsed_time(start_time, end_time);
}



void merge(double *A, int p, int q, int r)
{
    int i, j, k;
    int n1 = q - p +1;
    int n2 = r - q;
    double 
	*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] = 1.0 / 0.0; 	/* +inf */
    R[n2] = 1.0 / 0.0;  /* +inf */
    i = 0;
    j = 0;
    for (k = p; k <= r; k++) {
	if (L[i] <= R[j]) {
	  A[k] = L[i];
	  i++;
	}
	else {
	  A[k] = R[j];
	  j++;
	}
    }
    free(L);
    free(R);
    return;
}


void merge_sort(double *A, int p, int r)
{
    int q;
    if (p < r) { /* otherwise single element array */
	q = (int) floor(0.5 * (p + r));
	merge_sort(A, p, q);
	merge_sort(A, q+1, r);
	merge(A, p, q, r);
    }
}