#include<stdio.h>
void Merging(int arr[], int low, int mid, int high)
{
    int i = low;
    int j = mid+1;
    int k = low;
    int temp[high];

    while(i<=mid && j<=high)
    {
        if(arr[i] <= arr[j])
        {
            temp[k] = arr[i];
            i++;
            k++;
        }
        else
        {
            temp[k]  = arr[j];
            j++;
            k++;
        }
    }

    if(i>mid)
    {
        while(j<=high)
        {
            temp[k] = arr[j];
            j++;
            k++;
        }
    }
    else
    {
        while(i<=mid)
        {
            temp[k] = arr[i];
            i++;
            k++;
        }
    }

    for(k=low; k<=high; k++)
    {
        arr[k] = temp[k];
    }
}

void MergeSort(int arr[],int low, int high)
{
    if(low < high)
    {

        int mid = (low+high) /2;

        MergeSort(arr,low, mid);
        MergeSort(arr,mid+1, high);
        Merging(arr, low, mid, high);
    }
}

int main() {
    int n,i,s;
    printf("How many number you want to input :");
    scanf("%d",&n);
    printf("\n");
    int arr[n];
    for(i=0; i<n; i++)
    {
        printf("Input Value for Index %d = ",i);
        scanf("%d",&arr[i]);
    }

    MergeSort(arr, 0, n-1);

    printf("\n\nAfter Merge Sorting : ");
    for(i=0; i<n; i++)
    {
        printf("%d ",arr[i]);
    }
    printf("\n\n");

    return 0;
}