[排序]归并排序

注意

• 注意边界范围是$$ [l, r)$$
• 如果求解逆序数，需要保证cnt初始化为 0

说明

A[]为原数组，归并排序对 [l, r) 区间进行排序，

T[]为辅助数组，需要定义这样一个数组，作为参数传进去

使用方法

1. 定义辅助数组T[]，求逆序数的话需要将cnt置零
2. merge_sort(A, l, r, T); l为区间左端点，r为区间右端点的下一个点
3. 数组A中 [l, r) 已排好序

模板

归并排序

void merge_sort(int *A,int l,int r,int *T)
{
    if (r-l>1)
    {
        int m=l+(r-l)/2; //划分
        int p=l,q=m,i=l;
        merge_sort(A, l, m, T); //递归求解
        merge_sort(A, m, r, T); //递归求解
        while (p<m||q<r)
            if (q>=r||(p<m&&A[p]<=A[q]))
                T[i++]=A[p++]; //从左半数组复制到临时空间
            else
                T[i++]=A[q++]; //从右半数组复制到临时空间
        for (i=l; i<r; i++)
            A[i]=T[i]; //从辅助空间复制回A数组
    }
}

归并排序求逆序数

void merge_sort_inversion(int *A,int l,int r,int *T,int *cnt)
{
    if (r-l>1)
    {
        int m=l+(r-l)/2; //划分
        int p=l,q=m,i=l;
        merge_sort_inversion(A, l, m, T,cnt); //递归求解
        merge_sort_inversion(A, m, r, T,cnt); //递归求解
        while (p<m||q<r)
            if (q>=r||(p<m&&A[p]<=A[q]))
                T[i++]=A[p++]; //从左半数组复制到临时空间
            else
            {
                T[i++]=A[q++]; //从右半数组复制到临时空间
                *cnt += m-p;
            }
        for (i=l; i<r; i++)
            A[i]=T[i]; //从辅助空间复制回A数组
    }
}