三路快排，加随机优化

#include <iostream>
#include<ctime>

using namespace std;
const int N = 100010;
int p[N];
int n;

void insertionSort(int l, int r){
    for(int i= l+1; i<=r; i++){
        int temp = p[i];
        int j = i-1;
        for(;j>=0;j--){
            if(p[j] > temp){
                p[j + 1] = p[j];
            }
            else{
                /*
                for(int i=0;i<n;i++)
                    cout<<p[i]<<' ';
                cout<<endl;
                */
                break;
            }
        }
        p[j+1] = temp;
    }
}

void sort(int begin,int end){
    if(end - begin + 1 <= 15){
        insertionSort(begin, end);
        return;
    }
    srand(time(NULL));
    swap(p[begin], p[rand()%(end - begin)+ begin]);
    int l = begin;
    int r = end + 1;
    int mid = begin + 1;
    int temp = p[begin];
    while(mid < r){
        if(p[mid] == temp){
            mid++;
        }
        else if(p[mid] < temp){
            swap(p[++l], p[mid++]);
        }
        else{
            swap(p[--r], p[mid]);
        }
    }
    swap(p[begin], p[l]);
    sort(begin, l-1);
    sort(r, end);
}

using namespace std;
int main(){
    cin>>n;
    for(int i=0;i<n;i++)
        scanf("%d",&p[i]);
    sort(0,n-1);
    for(int j=0;j<n;j++)
        printf("%d ",p[j]);
    return 0;
}