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

#define N 10000000
#define BITS 16
#define MASK ((1 << BITS) - 1)
#define NIL -1

int v[N], w[N], next[N];
int head[1 << BITS];

void radixPass(int *a, int *b, int bits) {
  for (int i = 0; i <= MASK; i++) {
    head[i] = NIL;
  }
  for (int i = 0; i < N; i++) {
    int listNo = (a[i] >> bits) & MASK;
    next[i] = head[listNo];
    head[listNo] = i;
  }
  int pos = N - 1;
  for (int i = MASK; i >= 0; i--) {
    int l = head[i];
    while (l != NIL) {
      b[pos--] = a[l];
      l = next[l];
    }
  }
}

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(v, w, 0);
  radixPass(w, v, 16);

  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]);
  }
}