/*Program of sorting using merge sort through recursion*/

#include<stdio.h>
#define MAX 100

void merge_sort(int *arr, int left, int right)
{
	int mid;
	int temp[MAX];
	if(left<right)/* if more than one element*/
	{
		mid = (left+right)/2;
		merge_sort( arr, left , mid );  /* Sort arr[low:mid] */
		merge_sort( arr, mid+1, right );  /* Sort arr[mid+1:right] */
		/*Merge arr[low:mid] and arr[mid+1:right] to temp[left:right]*/
		merge( arr, temp, left, mid, mid+1, right ); 
		/* Copy temp[left:right] to arr[left:right] */ 
		copy(arr,temp,left, right);	
	}
}/*End of merge_sort*/

/*Merges arr[left1:right1] and arr[left2:right2] to temp[left1:right2]*/
void merge( int arr[], int temp[], int left1, int right1, int left2, int right2 )
{
	int i = left1;
	int j = left2 ;
	int k = left1 ;

	while( (i <= right1) && (j <=right2))
		temp[k++] = (arr[i]<=arr[j])? arr[i++]: arr[j++];
	while( i <= right1 )
		temp[k++]=arr[i++];
	while( j <= right2 )
		temp[k++]=arr[j++];
}/*End of merge()*/

void copy(int *arr, int *temp, int left, int right )
{
	for(int i=left; i<=right; i++)
		arr[i]=temp[i];
}


int main()
{
	int i, n, arr[MAX];
	
	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]);
	}

	merge_sort( arr, 0, n-1);

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