众所周知 sort() 函数非常智能，能够将时间复杂度稳定控制在一个极优的区间内。

于是我们稍微检索一下就可以知道，sort() 函数能够通过判断数组元素的分布特点来选择使用的排序算法，我们已知的较优的排序算法均被囊括其中。

显然，手写一个 $1$ 比 $1$ 的 sort() 函数是不太可能的。

那么，我们该如何在 sort() 的基础上写出一个更快且时间复杂度稳定的排序算法呢？

首先，我们学习一个叫做桶排序的算法，它是计数排序的升级版，能够在 $0 \le a_i < 10^9$ 的范围内适用。

桶排序的原理是：用桶来存储多个特定长度的区间内的数，如我们可以将区间长度设为 $10^2$，那么对于 $10^9$ 的数据，我们就只需要设置 $\frac{10^9}{10^2} = 10^7$ 个桶。我们让 $a_i \bmod 10^2$ 加入到第 $\lfloor \frac{a_i}{10^2} \rfloor$ 个桶之中，完成第一次分类。接着我们在对每个只有 $0 \le a_i < 10^2$ 范围的数进行第二次排序，但使用的是计数排序，每次将计数桶中的第 $p_i$ 个数增加 $1$，代表 $p$ 数组中 $p_i$ 的数量多了 $1$ 次。

但是，这样算法的缺点也比较明显，每次，我们都需要 $10^2$ 次运算去遍历这个计数桶，导致运算次数直接飙升到 $10^9$，会完全超时。

于是有人提出把区间长度调得更大，然后直接 sort() 一遍每个桶。如将区间长度调到 $10^3$，平均时间复杂度就是 $O(\frac{10^9}{10^3} \times \frac{10^3n}{10^9} \times \log \frac{10^3n}{10^9}) = O(n \log \frac{n}{10^3})$。

但是我们还不满足，因为如此一来当 $n = 10^7$ 、元素分布窄且密时我们无法跑过 $2 \times 10^8$（说人话就是这种桶排会被卡）。

于是我们思考：当一个桶内的数的数量 $k$ 满足 $k \log k \le 10^2$ 时，桶内使用 sort() 会更优；然而当 $k \log k > 10^2$ 时，我们使用计数排序。如此一来，我们的时间复杂度便稳定控制在了 $O(n \log 10^2) \approx O(n)$ 左右。

下面是具体实现代码，可能与上文有略微优化上的出入：

#include <cstdio>
#include <vector>
#include <algorithm>

const int MAXN = 10000005;

std::vector<int> v[MAXN];

int minn, maxn, k[105];

int main()
{
	freopen("sp.in", "r", stdin);
	freopen("sp.out", "w", stdout);
    int n, x;
    scanf("%d", &n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &x);
        int y = (x >> 2) / 25;
        minn = (minn < y) ? minn : y;
        maxn = (maxn > y) ? maxn : y;
        v[y].push_back(x);
    }
    for (int i = minn; i <= maxn; i++)
    {
        if (v[i].size() >= 23)
        {
            for (int j = v[i].size(); j; v[i].pop_back())
            {
                k[v[i][--j] % 100]++;
            }
            for (int j = 0; j < 100; j++)
            {
                for (; k[j]; k[j]--)
                {
                    v[i].push_back(j + (i << 2) + (i << 5) + (i << 6));
                }
            }
        }
        else
        {
        	std::sort(v[i].begin(), v[i].end());
		}
		for (int j = 0; j < v[i].size(); j++)
        {
            printf("%d ", v[i][j]);
        }
    }
    return 0;
}