// 1001b: sort 2^27 unsigned in place. 2-pass 16-bit LSD radix with 512MB buffer.
typedef unsigned int u32;
static u32 tmp[1 << 27];
static u32 cnt[65536];
void sort(unsigned *a, int n) {
u32 *p = (u32*)a;
for (int i = 0; i < 65536; i++) cnt[i] = 0;
for (int i = 0; i < n; i++) cnt[p[i] & 0xffff]++;
for (int i = 1; i < 65536; i++) cnt[i] += cnt[i-1];
for (int i = n - 1; i >= 0; i--) { u32 x = p[i]; tmp[--cnt[x & 0xffff]] = x; }
for (int i = 0; i < 65536; i++) cnt[i] = 0;
for (int i = 0; i < n; i++) cnt[tmp[i] >> 16]++;
for (int i = 1; i < 65536; i++) cnt[i] += cnt[i-1];
for (int i = n - 1; i >= 0; i--) { u32 x = tmp[i]; p[--cnt[x >> 16]] = x; }
}