mergesort_try2_:')

#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;
    for(int i = 0; i < s1; i++){
        p.push_back(v[i]);
    }
    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 = e2+1; i < v.size(); i++){
        p.push_back(v[i]);
    }
    v = p;
}

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;
}