//
// Stable in-place Merge Sort.
// Based on recursive implementation of block merging
//
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

void mergeSort(double* a, int n);

// The array a consists of 2 consecutive blocks of lengths
// len0 and len1 that are already sorted.
// Merge them in-place using the recursive procedure.
static void mergeBlocks(
    double* a,
    int len0, int len1
);

static void swapBlocks(double* a, int len0, int len1);
static void reverseArray(double* a, int n);
static void swap(double *p, double *q);

// The input array "a" is sorted.
// Find the element with minimal index i such that
// a[i] >= x
static int findUpper(
    const double* a, int n, double x
);

// The input array "a" is sorted.
// Find the element with maximal index i such that
// a[i] <= x
static int findLower(
    const double* a, int n, double x
);

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

int main() {
    printf("Stable in-place 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;
    }

    int len = 1;

    while (len < n) {

        /*...
        printf("Pass: len=%d\n", len);
        printArray(a, 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
            mergeBlocks(
                a + i, len, len2
            );
            // Go to the next pair
            i += (len + len2);
        }

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

        len *= 2;
    }
}

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

// The array a consists of 2 consecutive blocks of lengths
// len0 and len1 that are already sorted.
// Merge them in-place using the recursive procedure.
static void mergeBlocks(
    double* a,
    int len0, int len1
) {
    if (len0 <= 0 || len1 <= 0)
        return;
    int n = len0 + len1;

    if (len0 == 1) {
        /*...
        int i = 0;
        while (i < n-1 && a[i] > a[i+1]) {
            swap(&(a[i]), &(a[i+1]));
            ++i;
        }
        ...*/

        int k = findUpper(a+1, len1, a[0]);
        int i = 0;
        while (i < k) {
            assert(a[i] > a[i+1]);
            swap(&(a[i]), &(a[i+1]));
            ++i;
        }
        assert(i >= n-1 || a[i] <= a[i+1]);
        return;
    }

    if (len1 == 1) {
        /*...
        int i = n-1;
        while (i > 0 && a[i] < a[i-1]) {
            swap(&(a[i]), &(a[i-1]));
            --i;
        }
        ...*/

        int k = findLower(a, len0, a[n-1]);
        int i = n-1;
        while (i > k+1) {
            assert(a[i-1] > a[i]);
            swap(&(a[i-1]), &(a[i]));
            --i;
        }
        assert(i <= 0 || a[i-1] <= a[i]);
        return;
    }

    /*...
    printf("<<< Merge Blocks: len0=%d len1=%d\n", len0, len1);
    printArray(a, len0+len1);
    ...*/

    assert(len0 > 1 && len1 > 1);
    int c0, c1;
    if (len0 >= len1) {
        c0 = len0/2;
        c1 = findUpper(
            a+len0, len1, a[c0]
        );
        assert(len0+c1 >= n || a[len0+c1] >= a[c0]);

        swapBlocks(
            a+c0, len0-c0, c1
        );
    } else {
        c1 = len1/2;
        c0 =
            findLower(a, len0, a[len0+c1]) + 1;
        assert(c0 >= len0 || a[c0] >= a[len0+c1]);
        swapBlocks(
            a+c0, len0-c0, c1
        );
    }

    /*...
    printf("c0=%d c1=%d\n", c0, c1);
    printf("After swapBlocks:\n");
    printArray(a, len0+len1);
    ...*/

    mergeBlocks(
        a, c0, c1
    );
    mergeBlocks(
        a+c0+c1, len0-c0, len1-c1
    );

    /*...
    printf(">>> Merge Blocks finished: len0=%d len1=%d\n", len0, len1);
    printArray(a, len0+len1);
    ...*/
}

static void swapBlocks(double* a, int len0, int len1) {
    if (len0 <= 0 || len1 <= 0)
        return;
    if (len0 == len1) {
        for (int i = 0; i < len0; ++i)
            swap(&(a[i]), &(a[i+len0]));
        return;
    }
    reverseArray(a, len0);
    reverseArray(a+len0, len1);
    reverseArray(a, len0+len1);
}

static void reverseArray(double* a, int n) {
    if (n <= 1)
        return;
    int i = 0; int j = n-1;
    while (i < j) {
        swap(&(a[i]), &(a[j]));
        ++i; --j;
    }
}

// The input array "a" is sorted.
// Find the element with minimal index i such that
// a[i] >= x
static int findUpper(
    const double* a, int n, double x
) {
    if (n <= 0 || x <= a[0])
        return 0;
    if (x > a[n-1])
        return n;
    assert(n > 0 && a[0] < x && x <= a[n-1]);
    int b = 0; int e = n-1;
    while (e-b > 1) {
        assert(a[b] < x && x <= a[e]);
        int c = (b+e)/2;
        if (a[c] < x)
            b = c;
        else
            e = c;
    }
    assert(a[e-1] < x && x <= a[e]);
    return e;
}

// The input array "a" is sorted.
// Find the element with maximal index i such that
// a[i] <= x
static int findLower(
    const double* a, int n, double x
) {
    if (n <= 0 || x < a[0])
        return (-1);
    if (a[n-1] <= x)
        return n-1;
    assert(n > 0 && a[0] <= x && x < a[n-1]);
    int b = 0; int e = n-1;
    while (e-b > 1) {
        assert(a[b] <= x && x < a[e]);
        int c = (b+e)/2;
        if (a[c] <= x)
            b = c;
        else
            e = c;
    }
    assert(a[b] <= x && x < a[b+1]);
    return b;
}

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