月下刺猹。

正经排序算法。可轻松通过快排模板题。

实际上就是三路内省快排，求优化。

#include<bits/stdc++.h>
using namespace std;

template<typename T>
inline void __REACH_SORT(T arr[],const unsigned &len,const unsigned &depth,const unsigned &maxdep){
    if(len<=1)
        return;
    if(depth>maxdep){
        priority_queue<T,vector<T>,greater<T> > pq;
        for(unsigned Ith=0;Ith<len;++Ith)
            pq.push(arr[Ith]);
        unsigned Cur=0;
        while(pq.size()){
            arr[Cur]=pq.top();
            pq.pop();  
            ++Cur;
        }
        return;
    }   
    mt19937 mtRnd(chrono::system_clock::now().time_since_epoch().count());
    uniform_int_distribution<> dis(0,len-1);
    const T pv=arr[dis(mtRnd)];
    unsigned Ith(0),Jth(0),Kth(len);
    while(Ith<Kth){
        if(arr[Ith]<pv)
            swap(arr[Ith++],arr[Jth++]);
        else if(arr[Ith]>pv)
            swap(arr[Ith],arr[--Kth]);    
        else Ith++;    
    }
    __REACH_SORT(arr,Jth,depth+1,maxdep);
    __REACH_SORT(arr+Kth,len-Kth,depth+1,maxdep);
}

template<typename T>
inline void reach_sort(T arr[],const unsigned &len){
    __REACH_SORT(arr,len,0,floor(log2(len)));
}

int n,a[114514];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    reach_sort(a,n);
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    return 0;
}