/* Program to demonstrate non recursive merge sort */

/* Merge sort is an effective sorting algorithm which falls under divide and
conquer paradigm and produces a stable sort. Merge sort repeatedly breaks down a
list into several sublists until each sublist consists of a single element and
merging those sublists in a manner that results into a sorted list.

Bottom-Up Merge Sort Implementation:
The Bottom-Up merge sort approach uses iterative methodology. It starts with the
“single-element” array, and combines two adjacent elements and also sorting the
two at the same time. The combined-sorted arrays are again combined and sorted
with each other until one single unit of sorted array is achieved. */

#include <stdio.h>

void mergesort(int x[], int n);
void show(int x[], int n);

void mergesort(int x[], int n)
{
    int temp[50], i, j, k, lb1, lb2, ub1, ub2, size;

    size = 1;
    while (size < n)
    {
        lb1 = 0;
        k = 0;

        while (lb1 + size < n)
        {
            lb2 = lb1 + size;
            ub1 = lb2 - 1;
            if (ub1 + size < n)
                ub2 = ub1 + size;
            else
                ub2 = n - 1;

            i = lb1;
            j = lb2;

            while (i <= ub1 && j <= ub2)
                if (x[i] < x[j])
                    temp[k++] = x[i++];
                else
                    temp[k++] = x[j++];

            while (i <= ub1) temp[k++] = x[i++];

            while (j <= ub2) temp[k++] = x[j++];

            lb1 = ub2 + 1;
        }

        for (i = 0; i <= ub2; i++) x[i] = temp[i];

        size = size * 2;

        show(x, n);
    }
}

// function to show each pass
void show(int x[], int n)
{
    int i;
    for (i = 0; i < n; i++) printf("%d ", x[i]);
    printf("\n\n");
}

int main()  // main function
{
    int i, n, x[20];

    printf("Enter the number of elements: ");
    scanf("%d", &n);
    printf("Enter the elements:\n");
    for (i = 0; i < n; i++) scanf("%d", &x[i]);

    mergesort(x, n);

    printf("Sorted array is as shown:\n");
    for (i = 0; i < n; i++) printf("%d ", x[i]);
    return 0;
}

/* Output of the Program*/
/*
Enter the number of elements: 5
Enter the elements:
15
14
13
12
11
14 15 12 13 11

12 13 14 15 11

11 12 13 14 15

Sorted array is as shown:
11 12 13 14 15
*/