代码

#include <algorithm>
#include <type_traits>

using u32 = unsigned int;

template <class Iter>
void u32_sort(const Iter &a, const Iter &ed) {
  static_assert(std::is_same
    <typename std::iterator_traits<Iter>::value_type, u32>::value,
    "type must be uint32_t");
  int n = ed - a;
  if (n <= 128) {
    std::sort(a, ed);
    return;
  }
  u32 *b = new u32[n];
  static int cnt0[256], cnt8[256], cnt16[256], cnt24[256];
  std::fill(cnt0, cnt0 + 256, 0);
  std::fill(cnt8, cnt8 + 256, 0);
  std::fill(cnt16, cnt16 + 256, 0);
  std::fill(cnt24, cnt24 + 256, 0);
  Iter p;
  u32 *q;
  for (p = a; p != ed; ++p) {
    ++cnt0[*p & 255];
    ++cnt8[*p >> 8 & 255];
    ++cnt16[*p >> 16 & 255];
    ++cnt24[*p >> 24];
  }
  for (int i = 1; i < 256; ++i) {
    cnt0[i] += cnt0[i - 1];
    cnt8[i] += cnt8[i - 1];
    cnt16[i] += cnt16[i - 1];
    cnt24[i] += cnt24[i - 1];
  }
  for (p = a + n - 1; p - 7 >= a; p -= 8) {
    b[--cnt0[*p & 255]] = *p;
    b[--cnt0[p[-1] & 255]] = p[-1];
    b[--cnt0[p[-2] & 255]] = p[-2];
    b[--cnt0[p[-3] & 255]] = p[-3];
    b[--cnt0[p[-4] & 255]] = p[-4];
    b[--cnt0[p[-5] & 255]] = p[-5];
    b[--cnt0[p[-6] & 255]] = p[-6];
    b[--cnt0[p[-7] & 255]] = p[-7];
  }
  for (; p >= a; --p) b[--cnt0[*p & 255]] = *p;
  for (q = b + n - 1; q - 7 >= b; q -= 8) {
    a[--cnt8[*q >> 8 & 255]] = *q;
    a[--cnt8[q[-1] >> 8 & 255]] = q[-1];
    a[--cnt8[q[-2] >> 8 & 255]] = q[-2];
    a[--cnt8[q[-3] >> 8 & 255]] = q[-3];
    a[--cnt8[q[-4] >> 8 & 255]] = q[-4];
    a[--cnt8[q[-5] >> 8 & 255]] = q[-5];
    a[--cnt8[q[-6] >> 8 & 255]] = q[-6];
    a[--cnt8[q[-7] >> 8 & 255]] = q[-7];
  }
  for (; q >= b; --q) a[--cnt8[*q >> 8 & 255]] = *q;
  for (p = a + n - 1; p - 7 >= a; p -= 8) {
    b[--cnt16[*p >> 16 & 255]] = *p;
    b[--cnt16[p[-1] >> 16 & 255]] = p[-1];
    b[--cnt16[p[-2] >> 16 & 255]] = p[-2];
    b[--cnt16[p[-3] >> 16 & 255]] = p[-3];
    b[--cnt16[p[-4] >> 16 & 255]] = p[-4];
    b[--cnt16[p[-5] >> 16 & 255]] = p[-5];
    b[--cnt16[p[-6] >> 16 & 255]] = p[-6];
    b[--cnt16[p[-7] >> 16 & 255]] = p[-7];
  }
  for (; p >= a; --p) b[--cnt16[*p >> 16 & 255]] = *p;
  for (q = b + n - 1; q - 7 >= b; q -= 8) {
    a[--cnt24[*q >> 24]] = *q;
    a[--cnt24[q[-1] >> 24]] = q[-1];
    a[--cnt24[q[-2] >> 24]] = q[-2];
    a[--cnt24[q[-3] >> 24]] = q[-3];
    a[--cnt24[q[-4] >> 24]] = q[-4];
    a[--cnt24[q[-5] >> 24]] = q[-5];
    a[--cnt24[q[-6] >> 24]] = q[-6];
    a[--cnt24[q[-7] >> 24]] = q[-7];
  }
  for (; q >= b; --q) a[--cnt24[*q >> 24]] = *q;
  delete[] b;
}

void sort(u32 *a, int n) {
  u32_sort(a, a + n);
}

评测结果