代码

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

static u32 b[200000000];   // tmp buffer t[]
static u32 cnt[512];       // top-8 counts + per-segment histogram
static u32 start[257];     // segment boundaries

static inline void lsd_pass(u32 *S, u32 *D, int len, u32 *hist, int shift) {
  memset(hist, 0, 256*4);
  for (int i = 0; i < len; i++) hist[(S[i] >> shift) & 255]++;
  u32 s = 0;
  for (int i = 0; i < 256; i++) { u32 v = hist[i]; hist[i] = s; s += v; }
  for (int i = 0; i < len; i++) D[hist[(S[i] >> shift) & 255]++] = S[i];
}

void sort(unsigned *a, int n) {
  u32 *t = b;
  u32 *h = cnt;   // top-8 histogram
  memset(h, 0, 256*4);
  for (int i = 0; i < n; i++) h[a[i] >> 24]++;
  start[0] = 0;
  for (int i = 0; i < 256; i++) start[i+1] = start[i] + h[i];
  // split by top 8 bits into t[] (forward, stable)
  for (int i = 0; i < 256; i++) h[i] = start[i];
  for (int i = 0; i < n; i++) t[h[a[i] >> 24]++] = a[i];
  // per-segment LSD on low 24 bits (bytes 0,1,2)
  u32 *hist = cnt + 256;
  for (int k = 0; k < 256; k++) {
    int len = (int)(start[k+1] - start[k]);
    if (len == 0) continue;
    u32 *seg = t + start[k];
    u32 *seg2 = a + start[k];
    lsd_pass(seg, seg2, len, hist, 0);
    lsd_pass(seg2, seg, len, hist, 8);
    lsd_pass(seg, seg2, len, hist, 16);
  }
}

评测结果