//..................Merge Sort By 3 Portion...................
#include<iostream>
using namespace std;
void SubMerge(int a[],int l,int mid,int r);
void Merge(int a[],int l,int mid1,int mid2,int r)
{
SubMerge(a,l,mid1,mid2);
SubMerge(a,l,mid2,r);
}
void SubMerge(int a[],int l,int mid,int r)
{
int n1=(mid-l)+1,left[n1];
int n2=(r-(mid+1))+1,right[n2];
int i,j,k;
for (i=0, k=l; i<n1; i++, k++)
left[i]=a[k];
for (i=0, k=mid+1; i<n2; i++, k++)
right[i]=a[k];
i=0,j=0,k=l;
while(i<n1 && j<n2)
{
if(left[i]<right[j])
a[k]=left[i],i++;
else
a[k]=right[j],j++;
k++;
}
while(i<n1)
a[k]=left[i],i++,k++;
while(j<n2)
a[k]=right[j],j++,k++;
}
void MergeSort(int a[],int l,int r)
{
if (l<r)
{
int temp=(r-l)/3;
int mid1=l+temp;
int mid2=l+temp*2;
MergeSort(a,l,mid1);
MergeSort(a,mid1+1,mid2);
MergeSort(a,mid2+1,r);
Merge(a,l,mid1,mid2,r);
}
}
void display(int a[],int n)
{
for (int i=0; i<n; i++)
cout<<a[i]<<" ";
cout<<endl;
}
int main()
{
int n;
cout<<"ENTRE THE SIZE : ";
cin>>n;
int a[n];
cout<<"Enter Data : ";
for(int i=0; i<n; i++)
cin>>a[i];
int l=0,r=n-1;
cout<<"Unsorted Array : ";
display(a,n);
MergeSort(a,l,r);
cout<<"Sorted Array : ";
display(a,n);
}