代码

#pragma GCC optimize(3, "Ofast", "unroll-loops", "-funroll-loops")
#include<bits/stdc++.h>
using namespace std;

using i32 = int;
using i64 = long long;
using i128 = __int128;
using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = unsigned __int128;

void sort(unsigned *a, int n) {
  array<int, 65540> cnt {};
  vector<unsigned> aa(n);
  for (int i = 0; i < n; i++) {
    cnt[a[i] & 65535]++;
  }
  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];
  }
}

评测结果