#include<stdio.h>
#include<stdlib.h>

int n; //initial no. of integers in array
int *list; //pointer to the array of integers
int *MergeSort(int *A, int x, int y); //definition, return type is pointer to integer array


void main()
{
	printf("Enter the no. of integers in the array: ");
	scanf("%d",&n);
	
	list=(int *)malloc(n*sizeof(int));

	for(int i=0;i<n;i++) //taking input
	{	
		printf("\nEnter a no.: ");
		scanf("%d",&list[i]);
	}

	list=MergeSort(list,0,n-1); //calling MergeSort on list from index 0 to index n-1

	for(int i=0;i<n;i++) //printing output
	{	
		printf("%d ",list[i]);
	}
	
}

int *MergeSort(int *A, int x, int y) //declaration
{
	if(x==y) //base case, return the 1-element array itself
	{
		return A;
	}

	else
	{
		int size=1+y-x; //total no. of elements
		int half=(x+y)/2; //halving the array

		int halfsize=(size/2);
		int *A1=(int *)malloc(halfsize*sizeof(int));
		int *A2=(int *)malloc((size-halfsize)*sizeof(int));	
		A1=MergeSort(A, x, half);			//calling MergeSort on 1st half of array
		A2=MergeSort(A, half+1, y);		//calling MergeSort on 2nd half of array

		
		int *C;									//pointer to 3rd array
		C=(int *)malloc(size*sizeof(int));
		int j=0; 			//indicator for first half
		int k=0;			//indicator for 2nd half
		int i=0;			//indicator for 3rd array

		
		while((j<=half)&&(k<=half))			//till all the elements from either half are not exhausted
		{
			if(A1[j]<=A2[k])					//if element of first half is smaller, put that in C
			{
				C[i]=A1[j];
				j++;
			}
			else					//otherwise put element of second half in C
			{
				C[i]=A2[k];
				k++;
			}
			i++;				//increment indicator for C
		}
		int flag;
		if(j==(half+1))
		{
			flag=1;
		}
		else if(k==(half+1))
		{
			flag=2;
		}
		if(flag==1) 		//if first half is finished
		{
			while(i<size) 		//transfer all elements of second half in C
			{
				C[i]=A2[k];
				i++;
				k++;
			}
			
		}
		else if(flag==2) //if second half is finished
		{
			while(i<size) //transfer all elements of 1st half in C
			{
				C[i]=A1[j];
				i++;
				j++;
			}
		}
				
		
		for(int i=x;i<=y;i++) //copyback
		{
			A[x]=C[i-x];
		}
		free(A1);
		free(A2);
		free(C);
		return A;
	}
	

}