// 11-bit 3-pass LSD radix sort (11/11/10)
typedef unsigned u32;
static u32 tmp[100000000];
static u32 cnt[2048];
void sort(u32 *a, int n) {
u32 i;
for (i = 0; i < 2048; i++) cnt[i] = 0;
for (i = 0; i < (u32)n; i++) cnt[a[i] & 2047]++;
for (i = 1; i < 2048; i++) cnt[i] += cnt[i-1];
for (i = (u32)n; i-- > 0;) tmp[--cnt[a[i] & 2047]] = a[i];
for (i = 0; i < 2048; i++) cnt[i] = 0;
for (i = 0; i < (u32)n; i++) cnt[(tmp[i] >> 11) & 2047]++;
for (i = 1; i < 2048; i++) cnt[i] += cnt[i-1];
for (i = (u32)n; i-- > 0;) a[--cnt[(tmp[i] >> 11) & 2047]] = tmp[i];
for (i = 0; i < 2048; i++) cnt[i] = 0;
for (i = 0; i < (u32)n; i++) cnt[a[i] >> 22]++;
for (i = 1; i < 2048; i++) cnt[i] += cnt[i-1];
for (i = (u32)n; i-- > 0;) tmp[--cnt[a[i] >> 22]] = a[i];
for (i = 0; i < (u32)n; i++) a[i] = tmp[i];
}