//
// Recursive (top-down) implementation of 
// 2-Way Merge Sort
//
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

void mergeSort(double* a, int n);

static void mergeSortRecursively(
    double* a, int n,   // Input array
    double* b,          // Auxiliary memory
    int* arrayIdx       // In which array result is: 0 in a, 1 in b
);

static void merge(
    const double* a, int n,
    const double* b, int m,
    double* c
);

static void swap(double *p, double *q);

static void copyArray(const double* a, int n, double* b);

int main() {
    printf("Recursive (top-down) Merge Sort\n");

    int n, i;
    double *a = NULL;
    while (true) {
        printf("n:\n");
        if (scanf("%d", &n) < 1 || n <= 0)
            break;

        delete[] a;
        a = new double[n];

        for (i = 0; i < n; ++i) {
            a[i] = (double)(rand() % 100);
        }

        for (i = 0; i < n; ++i) {
            printf("%5.1lf", a[i]);
            if ((i+1) % 10 == 0)
                printf("\n");
        }
        printf("\n====\n");

        mergeSort(a, n);

        printf("Sorted:\n");

        for (i = 0; i < n; ++i) {
            printf("%5.1lf", a[i]);
            if ((i+1) % 10 == 0)
                printf("\n");
        }
        printf("\n====\n");
    }

    delete[] a;
    return 0;
}

void mergeSort(double* a, int n) {
    if (n <= 1)
        return;
    if (n == 2) {
        if (a[0] > a[1])
            swap(&(a[0]), &(a[1]));
        return;
    }

    double* b = new double[n];

    int arrayIdx;
    mergeSortRecursively(a, n, b, &arrayIdx);

    if (arrayIdx != 0) {
        // Result is in b
        copyArray(b, n, a);
    }

    delete[] b;
}

static void mergeSortRecursively(
    double* a, int n,   // Input array
    double* b,          // Auxiliary memory
    int* arrayIdx       // In which array result is: 0 in a, 1 in b
) {
    *arrayIdx = 0;
    if (n <= 1)
        return;
    if (n == 2) {
        if (a[0] > a[1])
            swap(&(a[0]), &(a[1]));
        return;
    }

    int k = n/2;
    int res0, res1;

    mergeSortRecursively(a, k, b, &res0);
    mergeSortRecursively(a+k, n-k, b+k, &res1);

    // Copy results to the same array, if necessary
    if (res1 != res0) {
        if (res0 == 0) {
            // Copy result to a
            copyArray(b+k, n-k, a+k);
        } else {
            // Copy result to b
            copyArray(a+k, n-k, b+k);
        }
    }

    if (res0 == 0) {
        merge(a, k, a+k, n-k, b);
    } else {
        merge(b, k, b+k, n-k, a);
    }

    *arrayIdx = 1 - res0;
}

static void merge(
    const double* a, int n,
    const double* b, int m,
    double* c
) {
    int i = 0;
    int j = 0;
    int k = 0;

    while (i < n && j < m) {
        if (a[i] <= b[j]) {
            c[k] = a[i]; ++i;
        } else {
            c[k] = b[j]; ++j;
        }
        ++k;
    }
    while (i < n) {
        c[k] = a[i]; ++k; ++i;
    }
    while (j < m) {
        c[k] = b[j]; ++k; ++j;
    }
}

static void swap(double *p, double *q) {
    double tmp = *p;
    *p = *q; *q = tmp;
}

static void copyArray(const double* a, int n, double* b) {
    for (int i = 0; i < n; ++i)
        b[i] = a[i];
}