Merge_Sort

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

#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define ll long long
#define ld long double
#define pb push_back
#define fe first
#define se second
#define nl "\n"
#define pp pair < ll , ll >
#define sz(x) (ll)x.size()
#define st(x) sort(x.begin(),x.end())
#define rst(x) sort(x.rbegin(), x.rend())
#define all(x) x.begin(),x.end()
long double pi = 3.14159265358979323;

const double EPS = 1e-12;
const int N = 1e6 + 5;
const int mod = 1e9 + 7;

ll arr[N];
ll n;


void merge(ll l ,ll mid , ll r){
        int n1 = mid - l + 1;
        int n2 = r - mid;
        int temp1[n1], temp2[n2];
        int l1 = l , m = mid , r1  = r ;
        for(int i = 0 ; i < n1 ; i++ ){
            temp1[i] = arr[l1];
            l1++;
        }
        m++;
        for(int i = 0 ; i < n2 ; i++ ){
            temp2[i] = arr[m];
            m++;
        }

        int i = 0 , j = 0 , k = l;
        while(i < n1 && j < n2){

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

        while(i < n1){
            arr[k] = temp1[i];
            i++ , k++;
        }

        while(j < n2){
            arr[k] = temp2[j];
            j++ , k++;
        }

}

void merge_sort(ll l , ll r){
    if(l == r){
        return;
    }
    ll mid = (l + r)/2;
    merge_sort(l,mid);
    merge_sort(mid + 1 , r);
    merge(l , mid , r);
}

void Print(){
    for(int i = 1 ;i <= n ; i++ ){
        cout << arr[i] << " ";
    }
    cout << "\n";
}
int main()
{
    fast;
    cin >> n ;
    for(int i = 1 ; i <= n ; i++ ){
        cin >> arr[i];
    }
    merge_sort(1,n);
    Print();





















    return 0;

}