代码

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

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

void sort(unsigned *a, int n) {
  u32 *c1 = cnt, *c2 = cnt + 256, *c3 = cnt + 512, *c4 = cnt + 768;
  u32 *t = b;
  memset(cnt, 0, 1024*4);
  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]++; }
  for (int j = 1; j < 256; j++) { c1[j]+=c1[j-1]; c2[j]+=c2[j-1]; c3[j]+=c3[j-1]; c4[j]+=c4[j-1]; }
  int i;
  for (i = n - 1; i >= 0; i--) {
    if (i >= 8) __builtin_prefetch(&t[c1[a[i-8] & 255]], 1);
    t[--c1[a[i] & 255]] = a[i];
  }
  for (i = n - 1; i >= 0; i--) {
    if (i >= 8) __builtin_prefetch(&a[c2[(t[i-8] >> 8) & 255]], 1);
    a[--c2[(t[i] >> 8) & 255]] = t[i];
  }
  for (i = n - 1; i >= 0; i--) {
    if (i >= 8) __builtin_prefetch(&t[c3[(a[i-8] >> 16) & 255]], 1);
    t[--c3[(a[i] >> 16) & 255]] = a[i];
  }
  for (i = n - 1; i >= 0; i--) {
    if (i >= 8) __builtin_prefetch(&a[c4[t[i-8] >> 24]], 1);
    a[--c4[t[i] >> 24]] = t[i];
  }
}

评测结果