#include <string.h>
typedef unsigned int u32;
static inline void insertion_sort(u32 *a, int lo, int hi) {
for (int i = lo + 1; i < hi; i++) {
u32 x = a[i];
int j = i - 1;
while (j >= lo && a[j] > x) { a[j+1] = a[j]; j--; }
a[j+1] = x;
}
}
static void afs(u32 *a, int lo, int hi, int shift) {
if (hi - lo <= 32) { insertion_sort(a, lo, hi); return; }
u32 cnt[256];
int start[256], next[256];
memset(cnt, 0, 256*4);
for (int i = lo; i < hi; i++) cnt[(a[i] >> shift) & 255]++;
int s = lo;
for (int k = 0; k < 256; k++) { start[k] = s; next[k] = s; s += cnt[k]; }
for (int i = lo; i < hi; i++) {
while (1) {
u32 x = a[i];
int k = (x >> shift) & 255;
if (i >= start[k] && i < start[k] + (int)cnt[k]) break;
int j = next[k]++;
u32 tmp = a[j]; a[j] = x; a[i] = tmp;
}
}
if (shift == 0) return;
for (int k = 0; k < 256; k++) {
int nl = start[k], nh = start[k] + (int)cnt[k];
if (nh - nl > 1) afs(a, nl, nh, shift - 8);
}
}
void sort(unsigned *a, int n) {
afs(a, 0, n, 24);
}