#include<stdio.h>

void merge(int *Y,int low,int mid,int high)
{
	int i,j,k,temp[100];
	i=low;
	j=mid+1;
	k=low;
	
	while((i<=mid)&&(j<=high))
	{
		if(Y[i]<=Y[j])
		{
			temp[k]=Y[i];
			i++;
			k++;
		}
		else
			temp[k++]=Y[j++];
	}
	
	while(i<=mid)
		temp[k++]=Y[i++];
	
	while(j<=high)
		temp[k++]=Y[j++];
	
	for(i=low;i<=high;i++)
		Y[i]=temp[i];
}

void merge_sort(int *Y, int low, int high)
{
	int mid;
	if(low<high)
	{
		mid=(low+high)/2;
		merge_sort(Y,low,mid);
		merge_sort(Y,mid+1,high);
		printf("\nLow=%d,mid=%d,High=%d",low,mid,high);
		merge(Y,low,mid,high);
	}
}

void print_array(int *Y,int n)
{
	int i;
	printf("\n\nArray of %d elements:",n);
	printf("\n\n%d",Y[0]);
	for(i=1;i<n;i++)
		printf(", %d",Y[i]);
}

void input_array(int *Y,int n)
{
	int i;
	printf("\n\nEnter %d elements:",n);
	for(i=0;i<n;i++)
		scanf("%d",&Y[i]);
}

void main()
{
	int X[100],n;
	printf("Enter number of elements:");
	scanf("%d",&n);
	if((n>0)&&(n<101))
	{
		input_array(X,n);
		printf("\nBefore Sorting:\n");
		print_array(X,n);
		merge_sort(X,0,n-1);//merge_sort(X,0,7)
		printf("\nAfter Merge Sorting:\n");
		print_array(X,n);
	}
	else
	{
		printf("\nInvalid Input");
	}
}