mergeSortVariant.cpp

#include<bits/stdc++.h>
// #define ll long long
#define int long long
#define mod 1000000007
using namespace std;


void merge(vector<int>& arr , int l , int mid , int r){

    vector<int> merged(r-l+1);

    int i=l, j=mid+1,k=0;

    while(i<=mid && j<=r){

        if(arr[i] <= arr[j]){
            merged[k] = arr[i];
            i++;
        }
        else{
            merged[k] = arr[j];
            j++;
        }
        k++;
    }

    while(i<=mid){
        merged[k]  = arr[i];i+=1;k+=1;
    }
     while(j<=r){
        merged[k]  = arr[j];j+=1;k+=1;
    }


    for(auto i:merged){
        arr[l++] = i;
    }

}



void mergeSort(vector<int>& arr , int l , int r){

    if(l >= r) return;

    int mid = (l+r)/2;

    mergeSort(arr , l , mid);
    mergeSort(arr , mid+1 , r);

    merge(arr , l, mid , r);
}


void solve(){

    int n;
    cin>>n;
    vector<int> v(n);

    for(int i=0;i<n;i++) cin>>v[i];

    mergeSort(v , 0 ,n-1);

    for(auto i:v) cout<<i<<" ";


}

int32_t main(){

    // #ifndef ONLINE_JUDGE
    //     freopen("input.txt", "r", stdin);
    //     freopen("output.txt", "w", stdout);
    // #endif

    int T=1;
    // cin>>T;
    while(T--){
        solve();
    }

}