#include 
#include 
#include 
#include 
using namespace std;

const int N = 100010;
int a[N];
int n;
void quick_sort(int a[],int l,int r){
    if(l >= r) return;
    swap(a[l],a[(l+r) >> 1]);
    int pivot = a[l],i = l,j = r;
    // n = 100000 且 数字全都一样，那么普通写法时间复杂度为O(n)
    while(i < j){
        while(a[j] > pivot &&  i < j) j--;
        a[i] = a[j];
        if(i < j) i++;
        while(a[i] < pivot && i < j) i++;
        a[j] = a[i];
        if(i < j) j--;
    }
    a[i] = pivot;
    quick_sort(a,l,i-1);
    quick_sort(a,i+1,r);
}

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


    return 0;
}

#include 
#include 
using namespace std;
const int N = 100010;
int a[N];
int n,k;

int quick_sort(int a[],int l,int r){
    if(l == r) return a[l];

    if(l < r){
        int pivot = a[l],i = l,j = r;
        while(i < j){
            while(a[j] > pivot && i < j) j--;
            a[i] = a[j];
            if(i < j) i++;
            while(a[i] < pivot && i < j) i++;
            a[j] = a[i];
            if(i < j) j--;
        }
        a[i] = pivot;
        if(i == k) return a[i];
        if(i > k) return quick_sort(a,l,i-1); // important
        if(i < k) return quick_sort(a,i+1,r);
    }
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> a[i];
    
    cout << quick_sort(a,1,n) << endl;
    return 0;
}

#include 
using namespace std;

const int N = 100010;
int n;
int a[N];
void merge_sort(int a[],int l,int r){
    if(l >= r) return; 
    int mid = (l+r) >> 1;
    merge_sort(a,l,mid);
    merge_sort(a,mid+1,r);

    int i = l,j = mid+1;
    int b[r-l+2],k = 0;
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) b[k++] = a[i++];
        else b[k++] = a[j++];
    }
    while(i <= mid) b[k++] = a[i++];
    while(j <= r) b[k++] = a[j++];
    for(int p = l,q = 0; p <= r; p++,q++){
        a[p] = b[q];
    }
}

int main(){
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    merge_sort(a,1,n);
    for(int i = 1; i <= n; i++) cout << a[i] << " ";
    return 0;
}

#include 
using namespace std;
typedef long long LL;
const int N = 100010;
int n;
int a[N];
LL res;

void merge_sort(int a[],int l,int r){
    if(l >= r) return;
    int mid = (l + r)  >> 1;
    merge_sort(a,l,mid);
    merge_sort(a,mid+1,r);
    
    int k = 0,i = l,j = mid+1;
    int temp[r-l+2];
    while(i <= mid && j <= r){
        if(a[i] <= a[j]) temp[k++] = a[i++];
        else {
            temp[k++] = a[j++];
            res += mid-i+1;
        }
    }
    //扫尾
    while(i <= mid) temp[k++] = a[i++];
    while(j <= r) temp[k++] = a[j++];
    //物归原主
    for(int p = l,q = 0; p <= r; p++,q++){
        a[p] = temp[q];
    }
}

int main(){
    
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> a[i];
    merge_sort(a,1,n);
    cout << res << endl;
    
    
    return 0;
}

必须是 l <= r,
不然 a1,a2 mid = a1下标, a1可以找到 a2会找不到

int binary_search(int a[],int l,int r,int target){
    while(l <= r){
        int mid = l + (r-l)/2;
        if(a[mid] == target) return mid;
        if(a[mid] < target) l = mid + 1;
        else r = mid - 1;
    }
    return -1;
}

// a[l] > target, 当target最小，l == r会死循环
// a[l] == target, 找到了，跳出来
int l_b(int a[],int l,int r,int target){
    while(l <= r){
        int mid = l + (r-l)/2;
        if(l == r && a[l] >= target) break;
        if(a[mid] < target) l = mid + 1;
        else r = mid; //等于时取最左边
    }
    return l;
}