#include<iostream.h>
#include<conio.h>

void Merge(int a[], int low, int mid, int high)
{					//Function to Merge Sorted Subsets of Array.
int temp[100],
    i=low,
    j=mid+1,
    k=low,s;

while(i<=mid && j<=high)
{
  if(a[i]<a[j])			//Compare Subsets.
  {
  temp[k]=a[i];			//Small Element will be stored in temp array.
  i++;
  }
  else
  {
  temp[k]=a[j];
  j++;
  }

k++;
}

if(i>mid)			//It will store any remaining elements in temp array.
{
   for(s=j;s<=high;s++)
   {
   temp[k]=a[s];
   k++;
   }
}
else
{
   for(s=i;s<=mid;s++)
   {
   temp[k]=a[s];
   k++;
   }
}

for(k=low;k<=high;k++)	//Copy Elements from temp array to Main array.
{
a[k]=temp[k];
}
}


void MergeSort(int a[], int low, int high)	//Function to split the Array into Subsets.
{
int mid;
if(low<high)		//Split the Array until Single Element is Left in each Sub part.
{
mid=(low+high)/2;		//Split Point (mid).

MergeSort(a,low,mid);
MergeSort(a,mid+1,high);
Merge(a,low,mid,high);	//Merge the Results.
}
}


void main()
{
clrscr();
int a[100],i,n,low,high;

cout<<"\n------- MERGE SORT -------\n\n";
cout<<"Enter the No. of Elements : ";
cin>>n;

cout<<"\nEnter Elements :\n";
for(i=1;i<=n;i++)
{
cin>>a[i];
}
low=1;
high=n;

MergeSort(a,low,high);			//Function Calling.

cout<<"\nAfter Sorting : \n";
for(i=1;i<=n;i++)
{
cout<<a[i]<<endl;
}
getch();
}