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


#include "merge_sort.h"


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


static 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);
    }
}