mergesort

#include <iostream>
#include <algorithm>
#include <vector>
#include <iterator>
#include <thread>
#include <math.h>
#include <time.h>

using namespace std;

typedef vector<int>::iterator it;

vector<int > buf(99999999);
vector<int > v;

void merge_sort(it l, it r){
    int d = distance(l, r);
    if(d<2) return;
    it m = l+d/2;

    it bufl = buf.begin() + (l - v.begin()), bufr = buf.begin() + (r - v.begin());

    merge_sort(l, m);
    merge_sort(m, r);

    merge(l, m, m, r, bufl);
    copy(bufl, bufr, l);
}

void p_merge_sort(vector<int > &v){
    vector<thread > threads(4);
    int d=ceil(v.size()/4.);

//    vector<thread > threads(2);
//    int d=ceil(v.size()/2.);
    it l=v.begin(), r=v.begin()+d;
    for(int i=0; i<4; i++){
        threads[i]=thread(merge_sort,l, r);
        advance(l, d);
        if(i<2)
            r=l+d;
        else
            r=v.end();
    }
//    for(int i=0; i<2; i++){
//        threads[i]=thread(merge_sort,l, r);
//        advance(l, d);
//        if(i<2)
//        {
//            r=l + d;
//        }
//        else
//        {
//            r=v.end();
//        }
//    }

    for(int i=0; i<4; i++)
        threads[i].join();
//    for(int i=0; i<2; i++)
//        threads[i].join();

    merge(v.begin(), v.begin()+d, v.begin()+d,
          v.begin()+2*d, buf.begin());

    merge(v.begin()+2*d, v.begin()+3*d, v.begin()+3*d,
          v.end(), buf.begin()+2*d);

    merge(buf.begin(), buf.begin()+2*d,
          buf.begin()+2*d, buf.begin()+v.size(), v.begin());

//    merge(v.begin(), v.begin()+d, v.begin()+d,
//////          v.begin()+2*d, buf.begin());
////
////    merge(buf.begin(), buf.begin()+2*d,
//          buf.begin()+2*d, buf.begin()+v.size(), v.begin());
}

int main(){
    int n;
    cin>>n;
    for(int j = 0; j < 10; j++)
    {
        for(int i = 0; i < n; i++){
            v.push_back(i);
        }
        for(int i = 0; i < n-1; i++){
            swap(v[i], v[rand() % (n - i - 1) + i + 1]);
        }
        clock_t begin = clock();
        p_merge_sort(v);
//        merge_sort(v.begin(), v.end());
        clock_t end = clock();
        double time_spent = (double)(end - begin) / CLOCKS_PER_SEC;
    //
        cout << time_spent << '\n';
    }
    return 0;
}