sort_Merge.cpp

#include<bits/stdc++.h>
using namespace std;

void merge(int a[],int l,int r,int mid)
{
    int leftSize=mid-l+1;
    int rightSize=r-(mid+1)+1;
    int Larr[leftSize+1];
    int Rarr[rightSize+1];
    for(int i=0; i<leftSize; i++)
    {
        Larr[i]=a[i+l];
    }
    for(int i=0; i<rightSize; i++)
    {
        Rarr[i]=a[i+mid+1];
    }
    Larr[leftSize]=Rarr[rightSize]=INT_MAX;
    int l_i=0;
    int r_i=0;
    for(int i=l; i<=r; i++)
    {
        if(Larr[l_i]<=Rarr[r_i])
        {
            a[i]=Larr[l_i];
            l_i++;

        }
        else
        {
            a[i]=Rarr[r_i];
            r_i++;
        }
    }
}



void mergeSort(int a[],int l,int r)
{
    if(l==r) return;
    int mid=(l+r)/2;
    mergeSort(a,l,mid);
    mergeSort(a,mid+1,r);
    merge(a,l,r,mid);
}



int main()
{
    int n;
    int a[n];
    scanf("%d",&n);
    for(int i=0; i<n; i++) scanf("%d",&a[i]);
    mergeSort(a,0,n-1);
    for(int i=0; i<n; i++) printf("%d ",a[i]);

}