/* 3(b). W.A.P. to sort the elements of a list of size 'n' using recursive mergesort. */

#include<stdio.h>
#include<conio.h>
int a[10],b[10];
void Merge(int low,int mid ,int high)
{
    int h=low,i=low,j=mid+1,q;
    while ((h <= mid) && (j <= high)) /* Sublists not exhausted yet */
    {
        if (a[h] <= a[j])
            b[i++] = a[h++];
        else
            b[i++] = a[j++];
    }
    if (h > mid) /* First sublist exhausted */
        for (q=j; q <= high; q++)
            b[i++] = a[q];
    else /* Second sublist exhausted */
    {
        for (q=h; q <= mid; q++)
            b[i++]=a[q];
    }
    for (q=low; q <= high; q++)
        a[q]=b[q]; /* Copy array b to array a */
}
void MergeSort(int low,int high)
{
    int mid;
    if (low < high)
    {
        mid = (low + high) / 2;
        MergeSort(low,mid);
        MergeSort(mid+1,high);
        Merge(low,mid,high);
    }
}
void main()
{
    int i,n;
    clrscr();
    printf("How many elements you wish to enter : ");
    scanf("%d",&n);
    printf("\nEnter %d elements : ",n);
    for (i = 0; i < n; i++)
        scanf("%d",&a[i]);
    MergeSort(0,n-1);
    printf("\nSorted list is as follows :\n");
    for (i=0; i < n; i++)
        printf("%d\n",a[i]);
    getch();
}
/* OUTPUT
How many elements you wish to enter : 5
Enter 5 elements : 32 52 12 65 23
Sorted list is as follows :
12
23
32
53
65
*/