#include <bits/stdc++.h>
#include <chrono>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <limits>
#include <vector>

using namespace std;
using namespace std::chrono;

void sortit(vector<int> &arr, int base = 1 << 15) {
    int n = arr.size();
    int modder = base - 1;
    vector<vector<int>> grps(base);
    vector<int> cnts(base + 1), live(base);
    for (int i = 0; i < n; i++) {
        int z = arr[i] >> 15;
        grps[arr[i] & modder].push_back(z);//adding each element in respective group
        cnts[z + 1]++;//increasing count
    }
    for (int i = 1; i < base; i++) cnts[i] += cnts[i - 1]; //making prefix array

    for (int i = 0; i < base; i++) {
        for (int &x : grps[i]) arr[cnts[x] + live[x]++] = (x << 15) + i;
    }
}


struct identity_extract {
    template<typename T>
    T operator()(const T &x) const {
        return x;
    }
};

// A stable sort that sorts in passes of `bits_per_pass` bits at a time.
template<typename T, typename T_extract_key = identity_extract>
void radix_sort(vector<T> &data, const T_extract_key &extract_key = identity_extract(), int bits_per_pass = 10) {
    if (data.empty() || int64_t(data.size()) * (64 - __builtin_clzll(data.size())) < 2 * (1 << bits_per_pass)) {
        stable_sort(data.begin(), data.end(), [&](const T &a, const T &b) -> bool {
            return extract_key(a) < extract_key(b);
        });
        return;
    }

    using T_key = decltype(extract_key(data.front()));
    T_key minimum = numeric_limits<T_key>::max(), maximum = numeric_limits<T_key>::lowest();

    for (T &x : data) {
        T_key key = extract_key(x);
        minimum = min(minimum, key);
        maximum = max(maximum, key);
    }

    int max_bits = minimum == maximum ? 0 : 64 - __builtin_clzll(maximum - minimum);
    int passes = max((max_bits + bits_per_pass / 2) / bits_per_pass, 1);

    if (64 - __builtin_clzll(data.size()) <= 1.5 * passes) {
        stable_sort(data.begin(), data.end(), [&](const T &a, const T &b) -> bool {
            return extract_key(a) < extract_key(b);
        });
        return;
    }

    vector<T> buffer(data.size());
    vector<int> counts;
    int bits_so_far = 0;

    for (int p = 0; p < passes; p++) {
        int bits = (max_bits + p) / passes;
        int bitmask = (1 << bits) - 1;
        counts.assign((1 << bits) + 1, 0);

        for (T &x : data) {
            T_key key = T_key(extract_key(x) - minimum);
            int key_section = int(key >> bits_so_far & bitmask);
            counts[key_section + 1]++;
        }

        for (int i = 1; i <= 1 << bits; i++)
            counts[i] += counts[i - 1];

        for (T &x : data) {
            T_key key = T_key(extract_key(x) - minimum);
            int key_section = int(key >> bits_so_far & bitmask);
            buffer[counts[key_section]++] = x;
        }

        data.swap(buffer);
        bits_so_far += bits;
    }
}
int main() {
    vector<int> a, b;
    for (int i = 1000; i <= 100000000; i *= 10) {
        cout << "Size " << i << " Sorting...." << endl;
        while (a.size() < i) {
            int x = rand() % (1 << 30);
            a.push_back(x);
            b.push_back(x);
        }
        auto t1 = high_resolution_clock::now();
        sortit(a);
        auto t2 = high_resolution_clock::now();
        radix_sort(b);
        auto t3 = high_resolution_clock::now();
        assert(a == b);

        cout << "\tTime taken by sortit() -> " << duration_cast<milliseconds> (t2 - t1).count() << "ms" << endl;
        cout << "\tTime taken by radix sort -> " << duration_cast<milliseconds> (t3 - t2).count() << "ms" << endl;
        cout << endl;
    }
}