/* Program of sorting using merge sort without recursion*/
#include<stdio.h>
#define MAX 30

main()
{
    int arr[MAX],temp[MAX],i,j,k,n,size,l1,h1,l2,h2;

    printf("Enter the number of elements : ");
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        printf("Enter element %d : ",i+1);
        scanf("%d",&arr[i]);
    }
    printf("Unsorted list is : ");
    for( i = 0 ; i<n ; i++)
        printf("%d ", arr[i]);

    /*l1 lower bound of first pair and so on*/
    for(size=1; size < n; size=size*2 )
    {
        l1=0;
        k=0;  /*Index for temp array*/
        while( l1+size < n)
        {
            h1=l1+size-1;
            l2=h1+1;
            h2=l2+size-1;
            if( h2>=n ) /* h2 exceeds the limlt of arr */
                h2=n-1;
            /*Merge the two pairs with lower limits l1 and l2*/
            i=l1;
            j=l2;
            while(i<=h1 && j<=h2 )
            {
                if( arr[i] <= arr[j] )
                    temp[k++]=arr[i++];
                else
                    temp[k++]=arr[j++];
            }
            while(i<=h1)
                temp[k++]=arr[i++];
            while(j<=h2)
                temp[k++]=arr[j++];
            /**Merging completed**/
            l1=h2+1; /*Take the next two pairs for merging */
        }/*End of while*/

        for(i=l1; k<n; i++) /*any pair left */
            temp[k++]=arr[i];

        for(i=0;i<n;i++)
             arr[i]=temp[i];

        printf("\nSize=%d \nElements are : ",size);
        for( i = 0 ; i<n ; i++)
            printf("%d ", arr[i]);
    }/*End of for loop */
    printf("Sorted list is :\n");
    for( i = 0 ; i<n ; i++)
        printf("%d ", arr[i]);
    printf("\n");
}/*End of main()*/