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


#define INFINITY 2.0

int merge(double *A, int p, int q, int r);
int merge_sort(double *A, int p, int r);
int merge_sort_random(double *A, int n);
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);
}

int main()
{
    int n, nmax = 2000;
    double *x = (double*) malloc(nmax * sizeof(double));
    srandom(time(NULL));
    for (n = 100; n < nmax; n += 10) {
	printf("%d,%d\n", n, merge_sort_random(x, n));
    }
    return 0;
}