代码

#define REP(i, s, e) for (register int i(s), end_##i(e); i <= end_##i; i++)
#include <bits/stdc++.h>

int L[10000], R[10000];
unsigned A[100000000], tmp[100000000];
struct cmp
{
	inline bool operator () (int x, int y) {return tmp[x] > tmp[y];}
};
std::priority_queue <int, std::vector <int>, cmp> q;

void sort(unsigned *a, int n)
{
	std::copy(a, a + n, tmp);
	const register int block = 1e4;
	int curl(0), curr(block);
	REP(i, 0, 1e4 - 1)
	{
		std::sort(tmp + curl, tmp + curr);
		L[i] = curl;
		R[i] = curr;
		q.push(curl);
		curl = curr;
		curr += block;
	}
	REP(i, 0, n - 1)
	{
		int x = q.top();
		q.pop();
		A[i] = tmp[x];
		if (x + 1 < R[x / block]) q.push(x + 1);
	}
	std::copy(A, A + n, a);
}

#ifdef CraZYali
int main()
{
	int n;
	std::cin >> n;
	unsigned int *a = new unsigned int[n];
	REP(i, 0, n - 1) std::cin >> a[i];
	sort(a, n);
	REP(i, 0, n - 1) std::cout << a[i] << ' ' ;std::cout<<std::endl;
}
#endif

评测结果