代码

// fused 8-bit 4-pass: count byte k+1 during scatter of byte k (wc2017b1 winner)
#include <string.h>
typedef unsigned int u32;
static u32 tmp[100000000];
static u32 cnt[1024];

void sort(u32 *a, int n) {
  u32 *c0 = cnt, *c1 = cnt + 256, *c2 = cnt + 512, *c3 = cnt + 768;
  u32 *t = tmp;
  memset(c0, 0, 1024);
  for (int i = 0; i < n; i++) c0[a[i] & 255]++;
  { u32 s = 0; for (int i = 0; i < 256; i++) { u32 v = c0[i]; c0[i] = s; s += v; } }
  for (int i = 0; i < n; i++) { u32 x = a[i]; t[c0[x & 255]++] = x; c1[(x >> 8) & 255]++; }
  { u32 s = 0; for (int i = 0; i < 256; i++) { u32 v = c1[i]; c1[i] = s; s += v; } }
  for (int i = 0; i < n; i++) { u32 x = t[i]; a[c1[(x >> 8) & 255]++] = x; c2[(x >> 16) & 255]++; }
  { u32 s = 0; for (int i = 0; i < 256; i++) { u32 v = c2[i]; c2[i] = s; s += v; } }
  for (int i = 0; i < n; i++) { u32 x = a[i]; t[c2[(x >> 16) & 255]++] = x; c3[x >> 24]++; }
  { u32 s = 0; for (int i = 0; i < 256; i++) { u32 v = c3[i]; c3[i] = s; s += v; } }
  for (int i = 0; i < n; i++) { u32 x = t[i]; a[c3[x >> 24]++] = x; }
}

评测结果