代码

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

评测结果