#include <cstdlib>
#include <vector>
#include <algorithm>
#include <thread>
#include <future>
int main()
{
std::vector<int> v(1ul<<27);
auto f(begin(v)), m(f+v.size()/2), l(end(v));
std::generate(f, l, rand);
#if 0
auto t1 = std::thread([&] () mutable { std::sort(f,m); } );
auto t2 = std::thread([&] () mutable { std::sort(m,l); } );
t1.join();
t2.join();
#else
auto f1 = std::async(std::launch::async, [&] () mutable { std::sort(f,m); } );
auto f2 = std::async(std::launch::async, [&] () mutable { std::sort(m,l); } );
f1.get();
f2.get();
#endif
std::inplace_merge(f,m,l);
}
I2luY2x1ZGUgPGNzdGRsaWI+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDx0aHJlYWQ+CiNpbmNsdWRlIDxmdXR1cmU+CgppbnQgbWFpbigpCnsKICAgIHN0ZDo6dmVjdG9yPGludD4gdigxdWw8PDI3KTsKCiAgICBhdXRvIGYoYmVnaW4odikpLCBtKGYrdi5zaXplKCkvMiksIGwoZW5kKHYpKTsKICAgIHN0ZDo6Z2VuZXJhdGUoZiwgbCwgcmFuZCk7CgojaWYgMAogICAgYXV0byB0MSA9IHN0ZDo6dGhyZWFkKFsmXSAoKSBtdXRhYmxlIHsgc3RkOjpzb3J0KGYsbSk7IH0gKTsKICAgIGF1dG8gdDIgPSBzdGQ6OnRocmVhZChbJl0gKCkgbXV0YWJsZSB7IHN0ZDo6c29ydChtLGwpOyB9ICk7CiAgICB0MS5qb2luKCk7CiAgICB0Mi5qb2luKCk7CiNlbHNlCiAgICBhdXRvIGYxID0gc3RkOjphc3luYyhzdGQ6OmxhdW5jaDo6YXN5bmMsIFsmXSAoKSBtdXRhYmxlIHsgc3RkOjpzb3J0KGYsbSk7IH0gKTsKICAgIGF1dG8gZjIgPSBzdGQ6OmFzeW5jKHN0ZDo6bGF1bmNoOjphc3luYywgWyZdICgpIG11dGFibGUgeyBzdGQ6OnNvcnQobSxsKTsgfSApOwogICAgZjEuZ2V0KCk7CiAgICBmMi5nZXQoKTsKI2VuZGlmCgogICAgc3RkOjppbnBsYWNlX21lcmdlKGYsbSxsKTsKfQo=