#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)) {
        using index_t = decltype(index);
        const auto mid = partition(begin, end, [](auto x) {
            return (x >> index_t::value & 1) == 0;
        });
        if constexpr (index_t::value > 0) {
            for (const auto& [from, to] : { pair { begin, mid }, pair { mid, end } })
                if (distance(from, to) > 1)
                    self(self, integral_constant<size_t, index_t::value - 1>{}, from, to);
        }
    };
    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;
}