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

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


main() 
{
    int i, n = 30;
    double x[] = {
	1.5, 45.5, 19.5, 42, 5, 26, 23, 26.5, 39.5, 4, 27.5, 34.5, 
	34, 12, 35.5, 50, 37, 46.5, 17.5, 25, 31, 47, 22.5, 44.5, 28.5, 
	5.5, 8, 41.5, 38, 48
    };
    merge_sort(x, 0, n-1);
    for (i = 0; i < n; i++) printf("%f\n", x[i]);
    return 0;
}


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[100], R[100];
    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++;
	}
    }
    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);
    }
}