// 2-pass 16-bit LSD radix sort
typedef unsigned u32;
static u32 tmp[100000000];
static u32 cnt[65536];
void sort(u32 *a, int n) {
u32 i;
for (i = 0; i < 65536; i++) cnt[i] = 0;
for (i = 0; i < (u32)n; i++) cnt[a[i] & 0xffff]++;
for (i = 1; i < 65536; i++) cnt[i] += cnt[i-1];
for (i = (u32)n; i-- > 0;) tmp[--cnt[a[i] & 0xffff]] = a[i];
for (i = 0; i < 65536; i++) cnt[i] = 0;
for (i = 0; i < (u32)n; i++) cnt[tmp[i] >> 16]++;
for (i = 1; i < 65536; i++) cnt[i] += cnt[i-1];
for (i = (u32)n; i-- > 0;) a[--cnt[tmp[i] >> 16]] = tmp[i];
}