#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;
}
 

I2luY2x1ZGUgPHN0ZGxpYi5oPgojaW5jbHVkZSA8c3RkaW50Lmg+CgojaW5jbHVkZSA8dGltZS5oPgojaW5jbHVkZSA8YXNzZXJ0Lmg+CgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8aW9zdHJlYW0+Cgp2b2lkIHJhZGl4X3NvcnQodWludDMyX3QgKmluLCB1aW50MzJfdCAqb3V0LCBpbnQgc2hpZnQsIGludCBuKXsKICAgIGludCBpbmRleFsyNTZdID0ge307CiAgICBmb3IgKGludCBpPTA7IGk8bjsgaSsrKSBpbmRleFsoaW5baV0+PnNoaWZ0KSYweEZGXSsrOwogICAgZm9yIChpbnQgaT0wLCBzdW09MDsgaTwyNTY7IGkrKykgc3VtICs9IGluZGV4W2ldLCBpbmRleFtpXSA9IHN1bSAtIGluZGV4W2ldOwogICAgZm9yIChpbnQgaT0wOyBpPG47IGkrKykgb3V0W2luZGV4WyhpbltpXT4+c2hpZnQpJjB4RkZdKytdID0gaW5baV07Cn0Kdm9pZCBjaGVjayhpbnQgbil7CiAgICB1aW50MzJfdCAqZGF0YSA9IG5ldyB1aW50MzJfdFtuXTsKICAgIHVpbnQzMl90ICp0ZW1wID0gbmV3IHVpbnQzMl90W25dOwogICAgdWludDMyX3QgKnNhbWUgPSBuZXcgdWludDMyX3Rbbl07CiAgICBmb3IgKGludCBpPTA7IGk8bjsgaSsrKSBzYW1lW2ldID0gZGF0YVtpXSA9IChyYW5kKCk8PDE2KXxyYW5kKCk7Ly8gTm90ZTogcmFuZCgpIG1pZ2h0IG5vdCBwcm9kdWNlIGVub3VnaCByYW5kb21uZXNzCgogICAgY2xvY2tfdCB0X3JhZGl4ID0gY2xvY2soKTsKCiAgICByYWRpeF9zb3J0KGRhdGEsIHRlbXAsICAwLCBuKTsKICAgIHJhZGl4X3NvcnQodGVtcCwgZGF0YSwgIDgsIG4pOwogICAgcmFkaXhfc29ydChkYXRhLCB0ZW1wLCAxNiwgbik7CiAgICByYWRpeF9zb3J0KHRlbXAsIGRhdGEsIDI0LCBuKTsKCiAgICB0X3JhZGl4ID0gY2xvY2soKSAtIHRfcmFkaXg7CgogICAgY2xvY2tfdCB0X3NvcnQgPSBjbG9jaygpOwoKICAgIHN0ZDo6c29ydChzYW1lLCBzYW1lK24pOwoKICAgIHRfc29ydCA9IGNsb2NrKCkgLSB0X3NvcnQ7CgogICAgc3RkOjpjb3V0IDw8ICJuOiAiIDw8IG4gPDwgc3RkOjplbmRsOwogICAgc3RkOjpjb3V0IDw8ICJyYWRpeF9zb3J0OiAiIDw8IHRfcmFkaXggPDwgc3RkOjplbmRsOwogICAgc3RkOjpjb3V0IDw8ICIgIHN0ZDpzb3J0OiAiIDw8IHRfc29ydCAgPDwgc3RkOjplbmRsOwogICAgc3RkOjpjb3V0IDw8IHN0ZDo6ZW5kbDsKCiAgICBmb3IgKGludCBpPTA7IGk8bjsgaSsrKSBhc3NlcnQoc2FtZVtpXSA9PSBkYXRhW2ldKTsKCiAgICBkZWxldGVbXSBkYXRhOwogICAgZGVsZXRlW10gdGVtcDsKICAgIGRlbGV0ZVtdIHNhbWU7Cn0KCmludCBtYWluKCl7CiAgICBmb3IgKGludCBpPTA7IGk8MzA7IGkrKykgY2hlY2soMTw8aSk7CiAgICByZXR1cm4gMDsKfQo=