代码

#include<bits/stdc++.h>
using namespace std;

void sort(unsigned *a, int n) {
  array<int, 65540> cnt {};
  unsigned *aa = (unsigned *)malloc(n * sizeof(unsigned));
  for (int i = 0; i < n; i++) {
    cnt[a[i] & 65536]++;
  }
  for (int i = 1; i < 65536; i++) {
    cnt[i] += cnt[i - 1];
  }
  for (int i = n - 1; ~i; i--) {
    aa[--cnt[a[i] & 65535]] = a[i];
  }
	cnt.fill(0);
  for (int i = 0; i < n; i++) {
    cnt[aa[i] >> 16]++;
  }
  for (int i = 1; i < 65536; i++) {
    cnt[i] += cnt[i - 1];
  }
  for (int i = n - 1; ~i; i--) {
    a[--cnt[aa[i] >> 16]] = aa[i];
  }
}

评测结果