#include <algorithm>
#include <cassert>
#include <chrono>
#include <functional>
#include <iomanip>
#include <iostream>
#include <parallel/algorithm>
#include <random>
#include <vector>

const int W = 22;

std::vector<int> original, sorted, tmp;

void f1() { std::ranges::sort(tmp); }

void f2() { std::ranges::stable_sort(tmp); }

void f3() { std::__parallel::sort(tmp.begin(), tmp.end()); }

void f4() { std::__parallel::stable_sort(tmp.begin(), tmp.end()); }

template<typename F> void test(F f)
{
    const int R = 33;
    std::chrono::duration<size_t, std::nano> rep[R];

    for (auto &r : rep)
    {
        tmp = original;
        auto start = std::chrono::high_resolution_clock::now();
        f();
        auto stop = std::chrono::high_resolution_clock::now();
        r = stop - start;
        assert(tmp == sorted);
    }
    std::nth_element(std::begin(rep), rep + R / 2, std::end(rep));
    std::cout << std::setw(W) << rep[R / 2].count();
}

int main()
{
    std::cout << std::setw(W / 2) << "size"
              << std::setw(W) << "sort"
              << std::setw(W) << "stable_sort"
              << std::setw(W) << "parallel::sort"
              << std::setw(W) << "parallel::stable_sort" << std::endl;

    for (int i = 1; i <= (1 << 19); i <<= 1)
    {
        original = sorted = tmp = std::vector<int>(i);

        std::random_device r;
        std::default_random_engine e(r());
        std::uniform_int_distribution<int> d(0, i);
        auto rng = std::bind(d, e);

        std::ranges::generate(original, rng);
        sorted = original;
        std::ranges::sort(sorted);

        std::cout << std::setw(W / 2) << i;

        test(f1);
        test(f2);
        test(f3);
        test(f4);

        std::cout << std::endl;
    }
}