代码

#include <string.h>
typedef unsigned int u32;

static u32 b[200000000];
static u32 cnt[5120];   // 2048 + 2048 + 1024

void sort(unsigned *a, int n) {
  u32 *c0 = cnt, *c1 = cnt + 2048, *c2 = cnt + 4096;
  u32 *t = b;
  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < n; i++) {
    u32 x = a[i];
    c0[x & 2047]++;
    c1[(x >> 11) & 2047]++;
    c2[x >> 22]++;
  }
  // prefix -> start positions
  u32 s0 = 0, s1 = 0, s2 = 0;
  for (int i = 0; i < 2048; i++) {
    u32 v0 = c0[i], v1 = c1[i];
    c0[i] = s0; s0 += v0;
    c1[i] = s1; s1 += v1;
  }
  for (int i = 0; i < 1024; i++) { u32 v2 = c2[i]; c2[i] = s2; s2 += v2; }

  for (int i = 0; i < n; i++) t[c0[a[i] & 2047]++] = a[i];
  for (int i = 0; i < n; i++) a[c1[(t[i] >> 11) & 2047]++] = t[i];
  for (int i = 0; i < n; i++) t[c2[a[i] >> 22]++] = a[i];
  for (int i = 0; i < n; i++) a[i] = t[i];
}

评测结果