#include<stdio.h>
#include<conio.h>
void simple_merge(int low,int mid,int high,int *a){
	int l=low;
	int m=mid+1;
	int temp[20];
	int k=0;
	while(l <= mid && m <= high){
		if(a[l]<= a[m]){
			temp[k++]=a[l];
			l++;
		}
		else{
			temp[k++]=a[m];
			m++;
		}
	}
	while(l<=mid){
		temp[k++]=a[l];
		l++;
	}
	while(m <= high){
		temp[k++]=a[m];
		m++;
	}
	k=0;
	while(low<=high){
		a[low]=temp[k++];
		low++;
	}
}
void merge_sort(int low,int high,int *a){
	if(low<high){
		int mid=(low+high)/2;
		merge_sort(low,mid,a);
		merge_sort(mid+1,high,a);
		simple_merge(low,mid,high,a);
	}
}
void main(){
	int a[20];
	int n;
	int i;
	clrscr();
	printf("Enter size of array\n");
	scanf("%d",&n);
	printf("Enter all array elements to sort\n");
	for(i=0;i<n;i++)
		scanf("%d",&a[i]);
	merge_sort(0,n-1,&a[0]);
	printf("The sorted values are\n");
	for(i=0;i<n;i++)
		printf("%d\n",a[i]);
	getch();
}