代码

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

static u32 b[200000000];      // 800MB scatter output
static u32 cnt[65536];        // high16 histogram
static u32 pos[65536];        // cursors
static u32 start[65537];      // bucket boundaries
static u32 seg8[256];         // per-bucket 8-bit histogram
static u32 scratch[8192];     // per-bucket scratch

void sort(unsigned *a, int n) {
  u32 *t = b;
  // pass 1: histogram of high16
  memset(cnt, 0, 65536*4);
  for (int i = 0; i < n; i++) cnt[a[i] >> 16]++;
  u32 s = 0;
  for (int k = 0; k < 65536; k++) { u32 v = cnt[k]; start[k] = s; pos[k] = s; s += v; }
  start[65536] = s;
  // pass 2: scatter by high16 (a -> t), stable
  for (int i = 0; i < n; i++) { u32 x = a[i]; t[pos[x >> 16]++] = x; }
  // pass 3: per-bucket sort by low16 (16-bit LSD), write into a
  for (int k = 0; k < 65536; k++) {
    int L = (int)(start[k+1] - start[k]);
    if (L == 0) continue;
    u32 *seg = t + start[k];
    u32 *out = a + start[k];
    // low8
    memset(seg8, 0, 256*4);
    for (int i = 0; i < L; i++) seg8[seg[i] & 255]++;
    u32 ss = 0;
    for (int j = 0; j < 256; j++) { u32 v = seg8[j]; seg8[j] = ss; ss += v; }
    for (int i = 0; i < L; i++) scratch[seg8[seg[i] & 255]++] = seg[i];
    // high8
    memset(seg8, 0, 256*4);
    for (int i = 0; i < L; i++) seg8[(scratch[i] >> 8) & 255]++;
    ss = 0;
    for (int j = 0; j < 256; j++) { u32 v = seg8[j]; seg8[j] = ss; ss += v; }
    for (int i = 0; i < L; i++) out[seg8[(scratch[i] >> 8) & 255]++] = scratch[i];
  }
}

评测结果