突然想到的 "分块"排序，时间复杂度 $O(n \sqrt n)$，虽然但是没什么用。

先对整个数列分成 $\sqrt n$ 块，对每一块冒泡排序，时间复杂度 $O(n\sqrt n)$。

对已经排好序的 $\sqrt n$ 块用一种类似双指针的做法合并，时间复杂度是 $O(n\sqrt n)$。

不知道有啥用，但是在分块哥眼里可能很好用 /kk

i64 n, s[MAXN], block, L[MAXN], R[MAXN], pos[MAXN];
std::vector <i64> ans;

struct BLOCK {
	std::vector <i64> t;
	
	inline void sort () noexcept {
		for (i32 i = t.size() - 1; ~i; i--)
			for (i32 j = 0; j + 1 <= i; j++)
				if (t[j] > t[j + 1])
					std::swap (t[j], t[j + 1]);
	}
} T[MAXN];

inline std::vector <i64> marge (std::vector <i64> a, std::vector <i64> b) noexcept{
	i64 l = 0, r = 0; std::vector <i64> nex;
	
	while (l < a.size() || r < b.size()){
		if (l >= a.size()) {nex.push_back (b[r++]); continue;}
		if (r >= b.size()) {nex.push_back (a[l++]); continue;}
		if (a[l] > b[r])
			nex.push_back (b[r++]);
		else
			nex.push_back (a[l++]);
	}
	
	return nex;
}

inline void init () noexcept{
	block = sqrt (n);
	for (i32 i = 1; i <= block; i++)
		L[i] = R[i - 1] + 1, R[i] = i * block;
	if (R[block] < n)
		++block, L[block] = R[block - 1] + 1, R[block] = n;
	
	for (i32 i = 1; i <= block; i++){
		for (i32 j = L[i]; j <= R[i]; j++)
			pos[j] = i, T[i].t.push_back(s[j]);
	}
}

int main() noexcept{
	read (n);
	for (i32 i = 1; i <= n; i++)
		read (s[i]);
	
	init ();
	for (i32 i = 1; i <= block; i++)
		T[i].sort (), ans = marge (ans, T[i].t);
		
	for (auto it : ans)
		print (it), putchar(' ');
    return 0;
}