/*Program to sort a given set of elements using the Merge sort method*/

#include<iostream.h>

	class Msort
		{
		private:
		     int a[10],n,low,high;

		public:
		     void readarray();
		     void rmsort();
		     void msort(int,int);
		     void Merge(int,int,int);
		     void display();
		};
	void Msort::readarray()
		{
		 cout<<"ENTER THE NUMBER OF ELEMENTS"<<endl;
		 cin>>n;
		 cout<<"ENTER THE ELEMENTS"<<endl;
		 for(int i=0;i<n;i++)
		     cin>>a[i];
		 low=0;
		 high=n-1;
		}
	void Msort::rmsort()
		{
		 msort(low,high);
		}
	 void Msort::msort(int low,int  high)
		{
			if(low<high)
			{
			 int mid=(low+high)/2;
			 msort(low,mid);
			 msort(mid+1,high);
			 Merge(low,mid,high);
			}
		}


	void Msort::Merge(int low,int mid,int high)
		{
		int i,j,k,b[15];
		k=i=low;
		j=mid+1;
		while((i<=mid) && (j<=high))
			{
			if(a[i]<a[j])
			   {
			     b[k]=a[i];
			     i++;
			     k++;
			   }
			else
			  {
			     b[k]=a[j];
			     j++;
			     k++;
			  }
			}
		while(i<=mid)
			{
			 b[k]=a[i];
			 i++;
			 k++;
			}
		while(j<=high)
			{
			 b[k]=a[j];
			 j++;
			 k++;
			}
		 for(int m=low;m<=high;m++)
		      a[m]=b[m];
		}

	void Msort::display()
		{
		 cout<<"THE SORTED ARRAY IS"<<endl;
		 for(int g=0;g<n;g++)
		     cout<<a[g]<<endl;
		}

	int main()
		{
		 Msort M;
		 M.readarray();
		 M.rmsort();
		 M.display();
		 return 0;
		}