#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <sys/time.h>
#include <time.h>

#define N 10000000
#define SELECTION_LIMIT 64
#define BITS 8
#define MASK ((1 << BITS) - 1)

int v[N];

void debug() {
  for (int i = 0; i < N; i++) {
    printf("%08x ", v[i]);
  }
  printf("\n");
}

void selectionSort(int lo, int hi) {
  int i, j, k, tmp;

  for (i = lo; i < hi; i++) {
    k = i;
    for (j = k + 1; j < hi; j++) {
      if (v[j] < v[k]) {
        k = j;
      }
    }
    tmp = v[i];
    v[i] = v[k];
    v[k] = tmp;
  }
}

void radixPass(int lo, int hi, int bits) {
  int ptr[1 << BITS], end[1 << BITS];
  for (int i = 0; i < (1 << BITS); i++) {
    end[i] = 0;
  }
  for (int i = lo; i < hi; i++) {
    end[(v[i] >> bits) & MASK]++;
  }
  ptr[0] = lo;
  end[0] += lo;
  for (int i = 1; i < (1 << BITS); i++) {
    ptr[i] = end[i - 1];
    end[i] += end[i - 1];
  }

  for (int i = 0; i < (1 << BITS); i++) {
    while (ptr[i] != end[i]) {
      int elem = v[ptr[i]];
      int bucket = (elem >> bits) & MASK;
      while (bucket != i) {
        int tmp = v[ptr[bucket]];
        v[ptr[bucket]++] = elem;
        elem = tmp;
        bucket = (elem >> bits) & MASK;
      }
      v[ptr[i]++] = elem;
    }
  }

  if (bits) {
    for (int i = 0; i < (1 << BITS); i++) {
      int size = end[i] - (i ? end[i - 1] : lo);
      if (size > SELECTION_LIMIT) {
        radixPass(end[i] - size, end[i], bits - BITS);
      } else if (size > 1) {
        selectionSort(end[i] - size, end[i]);
      }
    }
  }
}

int main(void) {
  timeval tv;

  srand(time(NULL));
  for (int i = 0; i < N; i++) {
    v[i] = rand();
  }

  gettimeofday (&tv, NULL);
  long long t1 = 1000LL * tv.tv_sec + tv.tv_usec / 1000;

  radixPass(0, N, 24);

  gettimeofday (&tv, NULL);
  long long t2 = 1000LL * tv.tv_sec + tv.tv_usec / 1000;
  printf("Timp: %lld ms\n", t2 - t1);

  for (int i = 1; i < N; i++) {
    assert(v[i] >= v[i - 1]);
  }
}