#include <stdlib.h>
#include <stdint.h>

#include <time.h>
#include <assert.h>

#include <algorithm>
#include <iostream>

void radix_sort(uint32_t *in, uint32_t *out, int shift, int n){
    int index[256] = {};
    for (int i=0; i<n; i++) index[(in[i]>>shift)&0xFF]++;
    for (int i=0, sum=0; i<256; i++) sum += index[i], index[i] = sum - index[i];
    for (int i=0; i<n; i++) out[index[(in[i]>>shift)&0xFF]++] = in[i];
}
void check(int n){
    uint32_t *data = new uint32_t[n];
    uint32_t *temp = new uint32_t[n];
    uint32_t *same = new uint32_t[n];
    for (int i=0; i<n; i++) same[i] = data[i] = (rand()<<16)|rand();// Note: rand() might not produce enough randomness

    clock_t t_radix = clock();

    radix_sort(data, temp,  0, n);
    radix_sort(temp, data,  8, n);
    radix_sort(data, temp, 16, n);
    radix_sort(temp, data, 24, n);

    t_radix = clock() - t_radix;

    clock_t t_sort = clock();

    std::sort(same, same+n);

    t_sort = clock() - t_sort;

    std::cout << "n: " << n << std::endl;
    std::cout << "radix_sort: " << t_radix << std::endl;
    std::cout << "  std:sort: " << t_sort  << std::endl;
    std::cout << std::endl;

    for (int i=0; i<n; i++) assert(same[i] == data[i]);

    delete[] data;
    delete[] temp;
    delete[] same;
}

int main(){
    for (int i=0; i<30; i++) check(1<<i);
    return 0;
}