#include <algorithm>
#include <cassert>
#include <iostream>
#include <random>
#include <vector>

template <class RandomAccessIterator>
void quick_sort(RandomAccessIterator begin, RandomAccessIterator end) {
    // 要素数0, 1の場合
    if (begin == end || begin + 1 == end) {
        return;
    }
    // 要素数2の場合
    if (begin + 2 == end) {
        if (*begin < *(begin + 1)) {
            return;
        } else {
            std::iter_swap(begin, begin + 1);
            return;
        }
    }
    // 要素数3以上の場合
    auto l = begin;
    auto r = end - 1;
    auto pivot = std::max({*l, *(l + 1), *(l + 2)});
    while (true) {
        while (*l < pivot) {
            ++l;
        }
        while (pivot < *r) {
            --r;
        }
        if (l < r) {
            std::iter_swap(l, r);
            ++l;
            --r;
        } else {
            break;
        }
    }
    quick_sort(begin, l);
    quick_sort(l, end);
}

int main() {
    // ユニットテストとテスト出力
    {
        std::vector<int> v = {6, 7, 8, 5, 9, 3, 1, 4, 8, 2, 2, 2, 0};
        quick_sort(v.begin(), v.end());
        if(!std::is_sorted(v.begin(), v.end())) {
            assert(false);
        }
        for (auto a : v) {
            std::cout << a << ", ";
        }
        std::cout << std::endl;
    }

    // ランダムテスト
    std::random_device seed_gen;
    std::mt19937 engine(seed_gen());
    std::uniform_int_distribution<> dist(0, 100);
    for (int i = 0; i < 1000; ++i) {
        std::vector<int> v;
        for (int j = 0; j < 1000; ++j) {
            v.push_back(dist(engine));
        }
        quick_sort(v.begin(), v.end());
        if(!std::is_sorted(v.begin(), v.end())) {
            for (auto a : v) {
                std::cout << a << ", ";
            }
            assert(false);
        }
    }
    std::cout << std::endl;

    std::cout << "success" << std::endl;
}