mergesort_try_:')

#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){
    int i1 = s1, i2 = s2;
    while(i1 <= e1){
        if(v[i1] >= v[i2]){
            swap(v[i1], v[i2]);
            int i = i2;
            while(i <= e2-1){
                if(v[i] > v[i+1]){
                    swap(v[i], v[i+1]);
                }
                i++;
            }
        }
        i1++;
    }
}

vector<int> 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(e-s == 1){
            if(v[s] > v[e]){
                swap(v[s], v[e]);
            }
        }
    }
    return v;
}

int main(){
    vector<int> v;
    for(int i = 0; i < 10000; i++){
        v.push_back(10000-i);
    }
    v = mergesort(v, 0, v.size()-1);
    printarray(v);
    return 0;
}