试了一下递减的序列，发现也可以。

就是说，先随机取 $k$ 对数 $(x,y)$，若 $a_x>a_y$ 就交换，然后插入排序。$k$ 取 $n\log n$ 时比较优秀。

#include<bits/stdc++.h>
using namespace std;
int a[100005];
namespace GenHelper
{
    unsigned z1,z2,z3,z4,b;
    unsigned rand_()
    {
    b=((z1<<6)^z1)>>13;
    z1=((z1&4294967294U)<<18)^b;
    b=((z2<<2)^z2)>>27;
    z2=((z2&4294967288U)<<2)^b;
    b=((z3<<13)^z3)>>21;
    z3=((z3&4294967280U)<<7)^b;
    b=((z4<<3)^z4)>>12;
    z4=((z4&4294967168U)<<13)^b;
    return (z1^z2^z3^z4);
    }
}
void srand(unsigned x)
{using namespace GenHelper;
z1=x; z2=(~x)^0x233333333U; z3=x^0x1234598766U; z4=(~x)+51;}
int read()
{
    using namespace GenHelper;
    int a=rand_()&32767;
    int b=rand_()&32767;
    return a*32768+b;
}
typedef unsigned long long ull;
typedef __uint128_t L;
struct FastMod//from KATCL
{
    ull b,m;
    FastMod(ull b): b(b),m(ull((L(1)<<64)/b)){}
    ull reduce(ull a)
    {
        ull q=(ull)((L(m)*a)>>64);
        ull r=a-q*b;
        return r>=b?r-b:r;
    }
}F(1);
int main()
{
	srand(19260817);
	int n,i,j,x,y,t;
	scanf("%d",&n);
	for(i=1;i<=n;i++)
		scanf("%d",&a[i]);
	F=FastMod(n);
	for(i=n*log2(n);i--;)
	{
		x=F.reduce(read())+1,y=F.reduce(read())+1;
		if(x>y) swap(x,y);
		if(a[x]>a[y]) swap(a[x],a[y]);
	}
	for(i=1;i<=n;i++)
	{
		t=a[i];
		for(j=i-1;j>=1;j--)
			if(a[j]>t)
				a[j+1]=a[j];
			else
				break;
		a[j+1]=t;
	}
	for(i=1;i<=n;i++)
		printf("%d ",a[i]);
}