无聊时候想出的一种排序方法，我算出的时间复杂度是 $O(n*log_2\sqrt n)$，但实际上会比堆排还慢一点点，个人认为是常数过大。

思想：将序列分成很多块，然后对每一块进行堆排，最后把所有的块合并在一起，结果保存在 $ans$ 数组里面。

代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 1;
int n, a[N], i, j, ans[N], cnt;
bool vis[N];

struct poi
{
	int n;
	friend bool operator < (poi a, poi b)
	{
		return ::a[a.n] > ::a[b.n];
	}
};

priority_queue<int> q;
priority_queue<poi> pq;


int main()
{
	cin >> n;
	for (i = 1; i <= n; ++i)
		cin >> a[i];
	int size = sqrt(n);
	for (i = 1; i + size - 1 <= n; i += size)
	{
		for (j = i; j < i + size; ++j)
			q.push(-a[j]);
		j = i;
		while (q.size())
			a[j] = -q.top(), q.pop(), ++j;
	}
	if (i + size - 1 != n)
	{
		i -= size;
		for (j = i; j <= n; ++j)
			q.push(-a[j]);
		j = i;
		while (q.size())
			a[j] = -q.top(), q.pop(), ++j;
	}
	for (i = 1; i + size - 1 <= n; i += size)
		pq.push(poi{i}), vis[i] = 1;
	if (i + size - 1 != n)
		pq.push(poi{i}), vis[i] = 1;
	while (pq.size())
	{
		int tmp = pq.top().n;
		ans[++cnt] = a[tmp], pq.pop();
		if (!vis[tmp + 1] && tmp < n)
			pq.push(poi{tmp + 1});
	}
	for (int i = 1; i <= n; ++i)
		cout << ans[i] << ' ';
	return 0;
}

想知道为什么会慢与直接堆排