#include<stdio.h>
#include<stdlib.h>
int main()
{
	int arr[100],n,i;
	printf("Enter the number of elements to sort\n");
	scanf("%d",&n);
	printf("Enter elements of array ");
	for(i=0;i<n;i++)
	{
		scanf("%d",&arr[i]);
	}
	printf("Before sorting array is :");
	for(i=0;i<n;i++)
	{
		printf("%d\n",arr[i]);
	}
	mergesort(arr,0,n-1);
	printf("After sorting array is :");
	for(i=0;i<n;i++)
	{
		printf("%d\n",arr[i]);
	}
        printf("\n");
}
void mergesort(int arr[],int beg,int end)
{
        if(beg<end)
	{
	int mid=(beg+end-1)/2;
        mergesort(arr,beg,mid);
        mergesort(arr,mid+1,end);
        merge(arr,beg,mid,end);
	}
}
void merge(int arr[],int beg,int mid,int end)
{
	int i,k,j;
	int n1=mid-beg+1;
	int n2=end-mid;
	int leftarr[n1],rightarr[n2];
	//copy the elements into temporary array
	for(i=0;i<n1;i++)
	{
		leftarr[i]=arr[beg+i];
	}
	for(j=0;j<n2;j++)
	{
		rightarr[j]=arr[mid+1+j];
	}
	i=0;
	j=0;
	k=beg;
	while(i<n1 && j<n2)
	{
		if(leftarr[i]<=rightarr[j])
		{

		arr[k]=leftarr[i];
		i++;
		}
		else
		{
			arr[k]=rightarr[j];
			j++;
		}
		k++;
	}
	while(i<n1)
	{
		arr[k]=leftarr[i];
		i++;
		k++;
	}
	while(j<n2)
	{
		arr[k]=rightarr[j];
		j++;
		k++;
	}
}