代码

#define REP(i, s, e) for (register int i(s), end_##i(e); i <= end_##i; i++)
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

int L[10000], R[10000];
unsigned A[100000000], tmp[100000000];

void sort(unsigned *a, int n)
{
	std::copy(a, a + n, tmp);
	struct cmp
	{
		inline bool operator () (int x, int y) {return tmp[x] > tmp[y];}
	};
	std::priority_queue <int, std::vector <int>, cmp> q;
	const register int block = sqrt(n);
	int curl(0), curr(block);
	REP(i, 0, n / block - 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

评测结果