代码

#include <algorithm>
#include <cstdlib>
#include <numeric>
#include <vector>

using u32 = unsigned;

template<class KeyFunc>
void counting_sorted(u32 *first, size_t n, u32 *dest, KeyFunc key) {
	
	using std::for_each_n;
	using std::exclusive_scan;

	size_t *rank = (size_t *) calloc(65536, sizeof(size_t));

	for_each_n(first, n, [&](u32 elem) {
		++rank[key(elem)];
	});
	exclusive_scan(rank, rank + 65536, rank, 0);
	for_each_n(first, n, [&](u32 elem) {
		dest[rank[key(elem)]++] = elem;
	});

	free(rank);
}

void sort(u32 *arr, int n) {
	u32 *tmp = (u32 *) malloc(n * sizeof(u32));
	counting_sorted(arr, n, tmp, [](u32 elem) { return elem & 65535; });
	counting_sorted(tmp, n, arr, [](u32 elem) { return (elem >> 16) & 65535; });
}

评测结果