// Quicksort using Djikstra's 3-way partition.

#include <functional>
#include <algorithm>
#include <random>
#include <chrono>
#include <iostream>
using namespace std;

int randint(int a, int b)
{
    thread_local default_random_engine re(random_device{}());
    uniform_int_distribution<> pick(a, b);
    return pick(re);
}

void timeit(function<void()> thunk)
{
    using clock = chrono::steady_clock;
    clock::time_point t = clock::now();
    thunk();
    chrono::duration<double> elapsed = clock::now() - t;
    cout << "Elapsed: " << fixed << elapsed.count() << "s\n";
}

template<typename In>
ostream& ostream_join(ostream& os, In first, In last, string sep)
{
    if (first != last)
    {
        for (;;)
        {
            os << *first;
            if (++first == last) break;
            os << sep;
        }
    }
    return os;
}

template<typename T>
ostream& operator<<(ostream& os, const vector<T>& a)
{
    os << '[';
    ostream_join(os, a.begin(), a.end(), ", ");
    os << ']';
    return os;
}

// Sort.

template<typename Bi, typename Compare, typename T>
pair<Bi, Bi> partition3(Bi first, Bi last, Compare comp, T pivot)
{
    for (Bi i = first; i != last;)
    {
        if (comp(*i, pivot))
        {
            iter_swap(first++, i++);
        }
        else if (comp(pivot, *i))
        {
            iter_swap(i, --last);
        }
        else
        {
            i++;
        }
    }
    return {first, last};
}

template<typename Ran, typename Compare>
void quicksort(Ran first, Ran last, Compare comp)
{
    if (auto n = distance(first, last); n >= 2)
    {
        auto eq = partition3(first, last, comp, *next(first, randint(0, n-1)));
        quicksort(first, eq.first, comp);
        quicksort(eq.second, last, comp);
    }
}

template<typename Ran>
void quicksort(Ran first, Ran last)
{
    quicksort(first, last, less<typename iterator_traits<Ran>::value_type>());
}

// Main.

void test1(int n)
{
    vector<int> t(n);
    generate(t.begin(), t.end(), bind(randint, 1-n, n-1));
    vector<int> u = t;
    sort(u.begin(), u.end());
    vector<int> v = t;
    quicksort(v.begin(), v.end());
    if (u == v)
    {
        cout << "Pass: " << n << endl;
    }
    else
    {
        cout << "Fail: " << n << endl;
        for (auto x : {t, u, v})
            cout << x << endl;
    }
}

void time1(int n)
{
    vector<int> t(n);
    generate(t.begin(), t.end(), bind(randint, 1-n, n-1));
    timeit([&]{
        quicksort(t.begin(), t.end());
    });
}

void p2call(int j, int k, function<void(int)> f)
{
    int m = 1;
    for (int i = 0; i < j; i++)
        m *= 2;
    for (int i = j; i < k; i++)
    {
        f(m-1);
        m *= 2;
    }
}

int main()
{
    p2call(0, 6, test1);
    p2call(16, 22, time1);
}