代码

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

static u32 b[200000000];
static u16 cnt16[131072];   // 2 x 65536 u16
static u32 h[1024];

void sort(unsigned *a, int n) {
  u16 *clo = cnt16, *chi = cnt16 + 65536;
  u32 *t = b;
  memset(cnt16, 0, sizeof(cnt16));
  for (int i = 0; i < n; i++) { u32 x = a[i]; clo[x & 0xFFFF]++; chi[x >> 16]++; }

  u32 *c0 = h, *c1 = h + 256, *c2 = h + 512, *c3 = h + 768;
  for (int k = 0; k < 256; k++) { c0[k] = 0; c1[k] = 0; c2[k] = 0; c3[k] = 0; }
  for (int bb = 0; bb < 65536; bb++) {
    c0[bb & 255] += clo[bb];
    c1[bb >> 8] += clo[bb];
    c2[bb & 255] += chi[bb];
    c3[bb >> 8] += chi[bb];
  }
  for (int i = 1; i < 256; i++) { c0[i]+=c0[i-1]; c1[i]+=c1[i-1]; c2[i]+=c2[i-1]; c3[i]+=c3[i-1]; }

  for (int i = n - 1; i >= 0; i--) t[--c0[a[i]&255]] = a[i];
  for (int i = n - 1; i >= 0; i--) a[--c1[(t[i]>>8)&255]] = t[i];
  for (int i = n - 1; i >= 0; i--) t[--c2[(a[i]>>16)&255]] = a[i];
  for (int i = n - 1; i >= 0; i--) a[--c3[t[i]>>24]] = t[i];
}

评测结果