代码

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

static u32 b[200000000];
static u32 cnt[1024];

static inline void scatter_fwd_pfw(u32 *S, u32 *D, int n, u32 *c, int shift) {
  int i = 0;
  for (; i + 16 < n; i++) {
    __builtin_prefetch(&D[c[(S[i + 16] >> shift) & 255]], 1, 3);
    D[c[(S[i] >> shift) & 255]++] = S[i];
  }
  for (; i < n; i++) D[c[(S[i] >> shift) & 255]++] = S[i];
}

void sort(unsigned *a, int n) {
  u32 *c1 = cnt, *c2 = cnt + 256, *c3 = cnt + 512, *c4 = cnt + 768;
  u32 *t = b;
  memset(cnt, 0, sizeof(cnt));
  for (int i = 0; i < n; i++) {
    u32 x = a[i];
    c1[x & 255]++;
    c2[(x >> 8) & 255]++;
    c3[(x >> 16) & 255]++;
    c4[x >> 24]++;
  }
  u32 s1 = 0, s2 = 0, s3 = 0, s4 = 0;
  for (int i = 0; i < 256; i++) {
    u32 v1 = c1[i], v2 = c2[i], v3 = c3[i], v4 = c4[i];
    c1[i] = s1; s1 += v1;
    c2[i] = s2; s2 += v2;
    c3[i] = s3; s3 += v3;
    c4[i] = s4; s4 += v4;
  }
  scatter_fwd_pfw(a, t, n, c1, 0);
  scatter_fwd_pfw(t, a, n, c2, 8);
  scatter_fwd_pfw(a, t, n, c3, 16);
  scatter_fwd_pfw(t, a, n, c4, 24);
}

评测结果