快速排序

void quicksort(int l,int r){
    if(l>=r)return;
    int i=l-1,j=r+1;
    int x=a[(l+r)>>1];
    while(i<j){
        do i++;while(a[i]<x);
        do j--;while(a[j]>x);
        if(i<j) swap(a[i],a[j]);
    }
    quicksort(l,j);
    quicksort(j+1,r);
}

结论：一轮快排下来的结果是$a[l..j]<=x，a[j+1..r]>x$（以j作为分界，可以根据代码推出）

注意点：

• 使用do while:保证两指针都移动，不然可能一直卡着没法停止
• 判断a[i]<x无等号：有等号可能会导致越界（如元素全为x）
• 判断i<j才互换a[i],a[j]（x的位置会变化，所以有可能i在x的右边，会越过j，需要判断）
• 边界l~j原因：原理为分治，不能分界成0和n，而j的范围是l到r-1

归并排序

void mergesort(int l,int r){
    if(l>=r)return;
    int m=(l+r)>>1;

    mergesort(l,m),mergesort(m+1,r);
    int t[r-l+1];
    int k=0,i=l,j=m+1;
    while(i<=m && j<=r){
        if(a[i]<a[j])t[k++]=a[i++];
        else t[k++]=a[j++];
    }
    while(i<=m) t[k++]=a[i++];
    while(j<=r) t[k++]=a[j++];

    for(int i=l;i<=r;++i){
        a[i]=t[i-l];
    }
}

理解：归并排序实质——递归将数组分为两个数组，默认已经排好序，按照大小顺序将其合并。因此先递归，返回时已是排好序

注意：

• 递归l-m和m+1-r原因：(l+r)>>1向下取整，m可能值为l
• 两个数组大小可能不一致，故一个排完后另一个直接复制

变形——求逆序数

if(a[i]<=a[j])t[k++]=a[i++];
        else{
            t[k++]=a[j++];
            cnt+=(m-l+1);
        }

原因：

• 在升序的数组中，逆序数为0
• 数组中一个连续段之间逆序对的交换，会影响段内的逆序数，但不会影响段外的逆序数，也不会影响段外和段内元素的逆序对
• 归并排序中，待归并时，两个数组都是升序，故可在归并时记录
• 当左边元素大于右边时，因为左边数组升序，可以知道其之后的元素均与右边元素构成逆序对
• 为什么不能用右边数组计数cnt+=（r-m）：在合并过程中有可能左边数组长度更大，用右边计数会导致左边有部分元素的逆序对算不上