#include <cstdlib>
#include <vector>
#include <algorithm>
#include <thread>
#include <future>
 
int main()
{
    std::vector<int> v(1ul<<27);
 
    auto const chunk = v.size()/4;
 
    auto f(begin(v)), l(end(v));
    std::generate(f, l, rand);
 
#if 0
    auto t1 = std::thread([&] () mutable { std::sort(f+chunk*0,f+chunk*1); } );
    auto t2 = std::thread([&] () mutable { std::sort(f+chunk*1,f+chunk*2); } );
    auto t3 = std::thread([&] () mutable { std::sort(f+chunk*2,f+chunk*3); } );
    auto t4 = std::thread([&] () mutable { std::sort(f+chunk*3,l        ); } );
    t1.join();
    t2.join();
    t3.join();
    t4.join();
#else
    auto f1 = std::async(std::launch::async, [&] () mutable { std::sort(f+chunk*0,f+chunk*1); } );
    auto f2 = std::async(std::launch::async, [&] () mutable { std::sort(f+chunk*1,f+chunk*2); } );
    auto f3 = std::async(std::launch::async, [&] () mutable { std::sort(f+chunk*2,f+chunk*3); } );
    auto f4 = std::async(std::launch::async, [&] () mutable { std::sort(f+chunk*3,l        ); } );
    f1.get();
    f2.get();
    f3.get();
    f4.get();
#endif
 
    std::inplace_merge(f,f+chunk*1,f+chunk*2);
    std::inplace_merge(f+chunk*2,f+chunk*3,l);
    std::inplace_merge(f,f+chunk*2,l);
}
 

I2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDx0aHJlYWQ+CiNpbmNsdWRlIDxmdXR1cmU+CgppbnQgbWFpbigpCnsKICAgIHN0ZDo6dmVjdG9yPGludD4gdigxdWw8PDI3KTsKCiAgICBhdXRvIGNvbnN0IGNodW5rID0gdi5zaXplKCkvNDsKCiAgICBhdXRvIGYoYmVnaW4odikpLCBsKGVuZCh2KSk7CiAgICBzdGQ6OmdlbmVyYXRlKGYsIGwsIHJhbmQpOwoKI2lmIDAKICAgIGF1dG8gdDEgPSBzdGQ6OnRocmVhZChbJl0gKCkgbXV0YWJsZSB7IHN0ZDo6c29ydChmK2NodW5rKjAsZitjaHVuayoxKTsgfSApOwogICAgYXV0byB0MiA9IHN0ZDo6dGhyZWFkKFsmXSAoKSBtdXRhYmxlIHsgc3RkOjpzb3J0KGYrY2h1bmsqMSxmK2NodW5rKjIpOyB9ICk7CiAgICBhdXRvIHQzID0gc3RkOjp0aHJlYWQoWyZdICgpIG11dGFibGUgeyBzdGQ6OnNvcnQoZitjaHVuayoyLGYrY2h1bmsqMyk7IH0gKTsKICAgIGF1dG8gdDQgPSBzdGQ6OnRocmVhZChbJl0gKCkgbXV0YWJsZSB7IHN0ZDo6c29ydChmK2NodW5rKjMsbCAgICAgICAgKTsgfSApOwogICAgdDEuam9pbigpOwogICAgdDIuam9pbigpOwogICAgdDMuam9pbigpOwogICAgdDQuam9pbigpOwojZWxzZQogICAgYXV0byBmMSA9IHN0ZDo6YXN5bmMoc3RkOjpsYXVuY2g6OmFzeW5jLCBbJl0gKCkgbXV0YWJsZSB7IHN0ZDo6c29ydChmK2NodW5rKjAsZitjaHVuayoxKTsgfSApOwogICAgYXV0byBmMiA9IHN0ZDo6YXN5bmMoc3RkOjpsYXVuY2g6OmFzeW5jLCBbJl0gKCkgbXV0YWJsZSB7IHN0ZDo6c29ydChmK2NodW5rKjEsZitjaHVuayoyKTsgfSApOwogICAgYXV0byBmMyA9IHN0ZDo6YXN5bmMoc3RkOjpsYXVuY2g6OmFzeW5jLCBbJl0gKCkgbXV0YWJsZSB7IHN0ZDo6c29ydChmK2NodW5rKjIsZitjaHVuayozKTsgfSApOwogICAgYXV0byBmNCA9IHN0ZDo6YXN5bmMoc3RkOjpsYXVuY2g6OmFzeW5jLCBbJl0gKCkgbXV0YWJsZSB7IHN0ZDo6c29ydChmK2NodW5rKjMsbCAgICAgICAgKTsgfSApOwogICAgZjEuZ2V0KCk7CiAgICBmMi5nZXQoKTsKICAgIGYzLmdldCgpOwogICAgZjQuZ2V0KCk7CiNlbmRpZgoKICAgIHN0ZDo6aW5wbGFjZV9tZXJnZShmLGYrY2h1bmsqMSxmK2NodW5rKjIpOwogICAgc3RkOjppbnBsYWNlX21lcmdlKGYrY2h1bmsqMixmK2NodW5rKjMsbCk7CiAgICBzdGQ6OmlucGxhY2VfbWVyZ2UoZixmK2NodW5rKjIsbCk7Cn0K

MDI6NDMgQU0vdG1wICUgbWFrZSAtQiAmYW1wOyZhbXA7IHRpbWUgLi90ZXN0CmcrKyAtc3RkPWMrKzB4IC1nIC1PMyAtSSB+L2N1c3RvbS9ib29zdC8gLW1hcmNoPW5hdGl2ZSB0ZXN0LmNwcCAtbyB0ZXN0IC1scHRocmVhZAoKcmVhbAkwbTUuMTkxcwp1c2VyCTBtMTIuNjAxcwpzeXMJMG0wLjI0NHMK

02:43 AM/tmp % make -B && time ./test
g++ -std=c++0x -g -O3 -I ~/custom/boost/ -march=native test.cpp -o test -lpthread

real	0m5.191s
user	0m12.601s
sys	0m0.244s