上期的 pdk 没找到有关资料，没学成，所以我自己发明了一个新算法，如果不了解的朋友可以看一下前情提要。

为了方便，我们把我发明的排序算法叫做 super_sort，让我们先大致了解一下 super_sort 的效率

	时间复杂度(最好/最差)	空间复杂度(最好/最坏)	稳定性
Super_sort	$O(1)/O(logn·\sqrt{n})$	O(n)	是

从表格中可以看出该算法的效率还不错，那么他是怎么工作的呢？这里我们采用归并排序，并使用桶排序和Tim_sort进行优化，让我们看看他的工作原理吧

STEP1: 找到序列中的最小值，让每个元素都减掉最小值

STEP2：定义 mid = (l + r) / 2 由于奇数个元素的序列的 mid 会偏左，所以我们让 l~mid 是左区间，mid+1~r 是右区间，这样就可以保证程序的稳定了。

STEP3：我们分别计算左区间和右区间的权值，权值等于元素的种类

例如：1 2 3 1 1 | 5 6 7 8 9 <- 数值

---------1 2 3 3 3 | 1 2 3 4 5 <- 权值

STEP4：对于元素种类少的进行桶排序，多的则判断它的长度是否大与基准值，基准值 = $max(2, \sqrt{n})$

STEP5：如果大于基准值则让右区间继续执行STEP1~STEP5，否则使用 Tim_sort 排序

STEP6：合并(归并)两组有序的序列，最终求解

接下来让大家看看代码(写了1个小时)

不喜勿喷，欢迎大佬来指点吐槽

code by xpg007:

#include <bits/stdc++.h>
using namespace std;
int a[1000001], sqrt_n, minn = 0x3f3f;
struct node{
	int start, end;
}point[1000001];
void t_sort(int l, int r){
	map<int, int> cnt;
	for (int i = l; i <= r; i++)
		cnt[a[i]]++;
	int pos = l;
	for (auto i = cnt.begin(); i != cnt.end(); i++)
		while (cnt[i->first]){
			a[pos++] = i->first;
			cnt[i->first]--;
		}
}
void add_all(int l, int mid, int r){
    int t[r - l + 1] = {0};
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r)
    	if (a[i] <= a[j])
    		t[k++] = a[i++];
    	else
    		t[k++] = a[j++];
    while (i <= mid)
        t[k++] = a[i++];
    while (j <= r)
        t[k++] = a[j++];
    for (k = 0, i = l; i <= r; i++, k++)
        a[i] = t[k];
}
void tim_sort(int l, int r){
    int len = 0;
    for (int i = l; i <= r; i += len){
        len = min(sqrt_n - 1, r - i + 1);
        if (len <= sqrt_n - 1) {
            for (int j = i; j < i + len; j++)
                for (int k = j; k > i && a[k] < a[k - 1]; k--)
                    swap(a[k], a[k - 1]);
        } else
            add_all(i, i + len / 2 - 1, i + len - 1);
    }
}
void my_sort(int l, int r){
	if (l == r)
		return ;
	int mid = (l + r) / 2;
	map<int, bool> m1;
	map<int, bool> m2;
	for (int i = l; i <= r; i++)
		if (i <= mid)
			m1[a[i]] = true;
		else
			m2[a[i]] = true;
	if (m1.size() < m2.size()){
		t_sort(l, mid);
		if (r - mid > sqrt_n)
			my_sort(mid + 1, r);
		else
			tim_sort(mid + 1, r);
		add_all(l, mid, r);
	} else {
		t_sort(mid + 1, r);
		if (mid - l + 1 > sqrt_n)
			my_sort(l, mid);
		else
			tim_sort(l, mid);
		add_all(l, mid, r);
	}
}
void init(int l, int r){
	for (int i = l; i <= r; i++)
		a[i] -= minn;
}
int main(){
	int n;
	cin >> n;
	sqrt_n = max(2, int(sqrt(n)));
	for (int i = 1; i <= n; i++){
		cin >> a[i];
		minn = min(minn, a[i]);
	}
	init(1, n);
	my_sort(1, n);
	for (int i = 1; i <= n; i++)
		cout << a[i] + minn << " ";
	return 0;
}

这里是函数对照表

t_sort	桶排序
add_all	归并
tim_sort	Tim 排序
my_sort	Super_Sort
init	集体削弱

看到这里(看在我写了1小时的代码，半小时的帖子)

给个小小的关注吧，求求啦~(支持互关)