#include <stdio.h>
#include <stdlib.h>


void radix (unsigned int a[], int n, unsigned int mask=1<<31) {

  int l, r;
  while (n > 1 && mask) {

    for (l=0, r=n-1;;) {
      while (l<=r && !(a[l]&mask)) ++l;

      while (l<=r && a[r]&mask)    --r;

      if (l>=r) break;

      // swap
      a[l]^=a[r]; a[r]^=a[l]; a[l]^=a[r];
    }

    mask>>=1; ++r;
    if (r < n-r) {

      radix (a, r, mask); a += r; n -= r;
    } else {

      radix (a+r, n-r, mask); n = r;
    }
  }
}

// test
int main() {
  unsigned int A[100];
  for (int i=0; i<100; i++) A[i] = rand()%100;

  radix (A, 100);  // sort numbers

  // output
  for (int i=0; i<100; i++) printf ("%i ", A[i]);

  printf ("\n");

  return 0;
}