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

void mergeSort(double* a, int n);

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

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

int main() {
    printf("Non-Recursive (down-top) 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];

    double *src = a;
    double *dst = b;
    int len = 1;

    while (len < n) {

        /*...
        printf("Pass: len=%d\n", len);
        printArray(src, n);
        ...*/

        int i = 0;
        while (i < n-len) {
            int len2 = len;
            if (i + len + len2 > n)
                len2 = n - (i + len);
            // Merge a pair of sub-arrays
            merge(
                src + i, len,
                src + i + len, len2,
                dst + i
            );
            // Go to the next pair
            i += len + len2;
        }

        // If number of sub-arrays is odd, then copy
        // the last sub-array to destination
        if (i < n)
            copyArray(src+i, n-i, dst+i);

        //... printArray(dst, n);

        len *= 2;

        // Swap source and destination
        double *tmp = src; src = dst; dst = tmp;
    }

    if (src != a)
        copyArray(b, n, a);

    delete[] b;
}

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];
}

static void printArray(const double* a, int n) {
    for (int i = 0; i < n; ++i) {
        printf("%5.1lf", a[i]);
        if ((i+1) % 10 == 0)
            printf("\n");
    }
    if (n % 10 != 0)
        printf("\n");
    printf("---\n");
}