代码

#include <string.h>

typedef unsigned int u32;

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

void sort(unsigned *a, int n) {
  u32 *c = cnt;
  u32 *tmp = b;

  // Pass 1: low 16 bits
  memset(c, 0, 65536 * 4);
  for (int i = 0; i < n; i++) c[a[i] & 0xFFFF]++;
  for (int i = 1; i < 65536; i++) c[i] += c[i-1];
  for (int i = n - 1; i >= 0; i--) tmp[--c[a[i] & 0xFFFF]] = a[i];

  // Pass 2: high 16 bits
  memset(c, 0, 65536 * 4);
  for (int i = 0; i < n; i++) c[tmp[i] >> 16]++;
  for (int i = 1; i < 65536; i++) c[i] += c[i-1];
  for (int i = n - 1; i >= 0; i--) a[--c[tmp[i] >> 16]] = tmp[i];
}

评测结果