#include <stdio.h>
#include <string.h>
#include <vector>

const int MAXN = 1e5 + 5;
const int MAXVAL = 1e6 + 5;
const int MAXNUM = 1e3;

int N;
int a[MAXN];
std::vector<int> block[MAXVAL + 5];

void insertion_sort(std::vector<int> &b) {
	int siz = b.size();
	if (siz == 0)
		return;
	for (int i = 1; i < siz; ++i) {
		int key = b[i];
		int j = i - 1;
		while (j >= 0 && b[j] > key) {
			b[j + 1] = b[j];
			--j;
		}
		b[j + 1] = key;
	}
}

int main(void) {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i)
		scanf("%d", a + i);
	for (int i = 1; i <= N; ++i)
		block[a[i] / MAXNUM].push_back(a[i]);
	for (int i = 0; i < MAXNUM + 5; ++i)
		insertion_sort(block[i]);
	for (int i = 0; i < MAXNUM + 5; ++i) {
		int siz = block[i].size();
		if (siz == 0)
			continue;
		for (int j = 0; j < siz; ++j)
			printf("%d ", block[i][j]);
	}
	return 0;
}

前两个点 WA 了，不知道为什么。。。

望高人指点。

（码风略丑，不喜勿喷）