代码

#include <bits/stdc++.h>
using namespace std;
vector<pair<unsigned,int> >v[1048579];
void sort(unsigned *a, int n) {
	int i,j=-1,k;
	vector<pair<unsigned,int> >::iterator it;
	for(i=0;i<n;++i){
		k=a[i]>>12,it=lower_bound(v[k].begin(),v[k].end(),pair<unsigned,int>{a[i],0});
		if(it->first==a[i])++it->second;
		else v[k].insert(it,pair<unsigned,int>{a[i],1});
	}
	for(i=0;i<1048576;++i){
		for(auto o:v[i]){
			for(k=o.second;k;--k)a[++j]=o.first;
		}
	}
}

评测结果