MergeSort

#include <iostream>
#include <vector>
using namespace std;

void printarray(vector<int> v){
    for(int i = 0; i < v.size(); i++){
        cout << v[i] << " ";
    }
    cout << "\n";
}

void merge(vector<int>& v, int s1, int e1, int s2, int e2){
    vector<int> p;
    int i1 = s1, i2 = s2;

    while(i1 <= e1 && i2 <= e2){
        if(v[i1] > v[i2]){
            p.push_back(v[i2]);
            i2++;
        } else{
            p.push_back(v[i1]);
            i1++;
        }
    }
    for(int i = i1; i <= e1; i++){
        p.push_back(v[i]);
    }
    for(int i = i2; i <= e2; i++){
        p.push_back(v[i]);
    }

    for(int i = s1; i <= e2; i++){
        v[i] = p[i-s1];
    }
}

void mergesort(vector<int>& v, int s, int e){
    if(e-s > 1){
        mergesort(v, s, s+(e-s)/2);
        mergesort(v, s+(e-s)/2+1, e);
        merge(v, s, s+(e-s)/2, s+(e-s)/2+1, e);
    } else{
        if(v[s] > v[e]){
            swap(v[e], v[s]);
        }
    }
}

int main(){
    vector<int> v;
    int n;
    cin >> n;
    while(n--){
        int x;
        cin >> x;
        v.push_back(x);
    }
    mergesort(v, 0, v.size()-1);
    printarray(v);
    return 0;
}