#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

template<class Iterator>
static constexpr void radix_sort(Iterator begin, Iterator end) noexcept {
    constexpr auto partition_recursive = [](auto self, auto index, auto begin, auto end) __attribute__((always_inline)) noexcept {
        using index_t = decltype(index);
        const auto mid = partition(begin, end, [](auto x) noexcept { return (x >> index_t::value & 1) == 0; });
        if constexpr (index_t::value > 0) {
            for (auto p : { false, true })
                if (distance(p ? mid : begin, p ? end : mid) > 1)
                    self(self, integral_constant<size_t, index_t::value - 1>{}, p ? mid : begin, p ? end : mid);
        }
    };
    partition_recursive(partition_recursive, integral_constant<size_t, (sizeof(typename Iterator::value_type) << 3) - 1>{}, begin, end);
}

int main() {
	vector<uint16_t> v(10 * 1000 * 1000);
	for (auto& n : v) n = rand() % numeric_limits<uint16_t>::max();
	cout << boolalpha << is_sorted(v.begin(), v.end()) << endl;
	radix_sort(v.begin(), v.end());
	cout << is_sorted(v.begin(), v.end()) << endl;
}