RT

大致就是分块+vector乱搞

就是整个vector分块，每个块长为 $\mathrm{blen}$，那么若数据的范围大小是 $\mathrm{len}$，则一共有 $\lceil\dfrac{\mathrm{len}}{\mathrm{blen}}\rceil$ 个块。每次根据 $a_i$ 的大小判断它在哪个块，然后二分插入的位置。这样插入数据的总复杂度是 $\mathcal{O}\!\left(n\log_2\!\mathrm{blen}\right)$。

取出的时候，就和普通的桶排一样，按顺序取出，复杂度 $\mathcal{O}\!\left(\max\!\left(\max a_i\;,n\right)\right)$ (?)

所以就是有没有人看一下复杂度是不是对的，还有块长取多少是最优的

如果实际上明显有更优的、可以取代本方法的排序算法那么是我sb