Merge_Sort

/*
    Was it all worth it ??
    In the end all it remains are just memories!!!

*/

#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;
//Just A Gentle Reminder about MOD
const int mod = 1e9 + 7;
void print(ll n , ll arr[]){

    for(int i = 1 ; i <= n ; i++ ){
        cout << arr[i] << " ";
    }
}

void merge(ll n , ll arr[] , ll l , ll mid , ll r){
        vector < ll > lt , rt;
        for(int i = l ; i <= mid ; i++ ){
            lt.pb(arr[i]);
        }

        for(int i = mid + 1 ; i <= r ; i++ ){
            rt.pb(arr[i]);
        }

        int i = 0 , j = 0 , k = l;
        while(i < sz(lt) && j < sz(rt)){

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

        while(i < sz(lt)){
            arr[k] = lt[i];
            i++ , k++;
        }

        while(j < sz(rt)){
            arr[k] = rt[j];
            j++ , k++;
        }
}

void merge_sort(ll n , ll arr[] , ll l , ll r){

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


int main()
{
    fast;
    ll n;
    cin >> n ;
    ll arr[n+1];
    for(int i = 1 ; i <= n ;i++ ){
              cin >> arr[i];
    }
    merge_sort(n,arr ,1,n);
    cout << "merge_sort\n";
    print(n,arr);
    //Time - Complexity - O(nlogn)
    //Best - O(nlogn) - when array is already sorted
    //Worst - O(nlogn) when array is reverse sorted
    //Space Complexity - O(n)
    //O(n) extra space is needed





















    return 0;
//It's not end it yet
}