#include <algorithm>
#include <iostream>
#include <numeric>
#include <random>
#include <vector>
#include <future>
#include <execution>
#include <chrono>
using namespace std;

/*#define PROFILE_CONCAT_INTERNAL(X, Y) X##Y
#define PROFILE_CONCAT(X, Y) PROFILE_CONCAT_INTERNAL(X, Y)
#define UNIQUE_VAR_NAME_PROFILE PROFILE_CONCAT(profileGuard, __LINE__)
#define LOG_DURATION(x) LogDuration UNIQUE_VAR_NAME_PROFILE(x)
#define LOG_DURATION_STREAM(x, y) LogDuration UNIQUE_VAR_NAME_PROFILE(x, y)*/

/*class LogDuration {
public:
    // заменим имя типа std::chrono::steady_clock
    // с помощью using для удобства
    using Clock = std::chrono::steady_clock;

    LogDuration(const std::string& id, std::ostream& dst_stream = std::cerr)
        : id_(id)
        , dst_stream_(dst_stream) {
    }

    ~LogDuration() {
        using namespace std::chrono;
        using namespace std::literals;

        const auto end_time = Clock::now();
        const auto dur = end_time - start_time_;
        dst_stream_ << id_ << ": "s << duration_cast<milliseconds>(dur).count() << " ms"s << std::endl;
    }

private:
    const std::string id_;
    const Clock::time_point start_time_ = Clock::now();
    std::ostream& dst_stream_;
};*/

template <typename It>
void PrintRange(It range_begin, It range_end) {
    for (auto it = range_begin; it != range_end; ++it) {
        cout << *it << " "s;
    }
    cout << endl;
}

template <typename RandomIt>
void MergeSort(const RandomIt &range_begin,const RandomIt &range_end) {
    if (range_end - range_begin < 2) return;

    RandomIt mid = range_begin + (range_end - range_begin) / 2;

    MergeSort(range_begin, mid);

    auto future1 = std::async( [&]{
        MergeSort( mid, range_end);
    });
    future1.get();
    std::inplace_merge(range_begin, mid, range_end);
}
int main() {
    //LOG_DURATION("vector w/o reserve");
    mt19937 generator;
    vector<int> test_vector(1000);
    iota(test_vector.begin(), test_vector.end(), 1);
    shuffle(test_vector.begin(), test_vector.end(), generator);
    PrintRange(test_vector.begin(), test_vector.end());
    MergeSort(test_vector.begin(), test_vector.end());
    PrintRange(test_vector.begin(), test_vector.end());
    MergeSort(test_vector.data(), test_vector.data() + test_vector.size());
    return 0;
}