深入理解归并排序——从归并排序到CDQ分治、归并树

归并排序

首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。

//将有序数组a[]和b[]合并到c[]中  
void merge(int a[], int n, int b[], int m, int c[]) {
    int i, j, k;  
    i = j = k = 0;  
    while (i < n && j < m) {  
        if (a[i] < b[j]) c[k++] = a[i++];  
        else c[k++] = b[j++];   
    }  
    while (i < n) c[k++] = a[i++];  
    while (j < m) c[k++] = b[j++];  
}  
           

可以发现合并有序数列的效率是非常高的，有O(N)此时N = len(a)+len(b)。

这里是我的个人网站：

https://endlesslethe.com/mergesort-and-mergetree-tutorial.html

有更多总结分享，排版也可能会更好看一点=v=

加上一点分治的想法：

从而对于一个数组，我们可以如下的方式二分分治：

如上图所示，最下面是我们需要排序的数组。我们把它分成N个长度为1的区间。那么相邻两个区间进行一次合并的时间为\(O(N)\)。而得到有序的、长度为2的区间后，我们根据它们有序的特点继续合并，那么又在\(O(N)\)的时间内得到了有序的、长度为4的区间。

显然当我们得到最后的排序结果时，一共用了\(O(NlogN)\)的时间，\(O(NlogN)\)的空间。

写成伪代码的形式：

实现代码

下面是归并排序程序的调用程序，但前面的merge函数需要稍加修改:

• 对a的两个区间进行归并（起点不同）
• temp的结果需要写回到a中，数组a和temp作为全局变量传入

void mergesort(int l, int r) {  
    if (l < r) {  
        int mid = (first + last) / 2;  
        mergesort(first, mid);    //左边有序  
        mergesort(mid + 1, last); //右边有序  
        merge(first, mid, last); //再将二个有序数列合并  
    }  
}  

void merge(int l,int m,int r)   {
    int i = l;  
    int j = m + 1;  
    int k = l;  
    while(i <= m && j <= r) {  
        if(a[i] > a[j]) tmp[k++] = a[j++];
        else tmp[k++] = a[i++];  
    }  
    while(i <= m) tmp[k++] = a[i++];  
    while(j <= r) tmp[k++] = a[j++];  
    for(int i=l;i<=r;i++)  
        a[i] = tmp[i];  
}  
           

时间复杂度分析

一共\(logN\)层，每一层都花费\(O(N)\)的时间，故总的时间复杂度为\(O(NlogN)\)

正确性证明

简单地使用loop-invariant technique [R. W. Floyd, 1967]（数学归纳法）即可证明。

归并排序求逆序数

通常我们都是通过树状数组计算逆序数的数量。而现在我们通过归并排序的分治也可以解决这个问题。

从逆序数的定义我们可以知道，对于\(a_i\)来说，不妨记当前index为pos2， 排序好的位置是pos1，这里保证pos1<pos2（这样所有统计逆序数的过程都是从后向前交换的过程，而不是向前和向后混合的复杂情况）。那它的逆序数个数就是从pos2逐个交换到pos1过程中，遇到的大于\(a_i\)的数的个数。

考虑归并排序的特点，现在因为归并排序已经将左右两侧的元素都排序好了，所以两侧内部的逆序数为0，只需要考虑异侧的情况。而异侧的逆序数对数如何统计呢？我们可以简单地在merge时统计——所有在右侧的元素\(a_i\)，当其被插入到pos1位置时，它所遇到的所有数都是大于\(a_i\)的，因为这个数列merge后是有序的。故根据逆序数的定义，在这个子区间中#逆序数(\(a_i\))=pos2-pos1。

实现代码

int a[MAXN];
int tmp[MAXN];

int mergesort(int l, int r) {
    if (r < l) return 0;
    if (r == l) return 0;
    int mid = l + ((r-l)>>1);

    int n_l = mergesort(l, mid);
    int n_r = mergesort(mid+1, r);

    int pl = l, pr = mid+1;
    int count = 0;
    for (int i = l; i <= r; i++) {
        // 每当右边元素插入到tmp数组时，就要计算逆序数
        if (pl > mid) tmp[i] = a[pr++];
        else if (pr > r) tmp[i] = a[pl++];
        else if (a[pl] <= a[pr]) tmp[i] = a[pl++];
        else {
            count += pr - i;
            tmp[i] = a[pr++];
        }
    }
    // 将排序结果放到a里
    for (int i = l; i <= r; i++) a[i] = tmp[i];
    return count + n_l + n_r;
}
           

归并排序（求逆序数）和CDQ分治

CDQ分治的基本思想十分简单：普通分治在合并两个子问题的过程中，[L,M]内的问题不会对[M+1,R]内的问题产生影响，比如线段树的求和、求极值。而CDQ分治合并两个子问题，同时考虑到[L,M]内的修改对[M+1,R]内的查询产生的影响。归并排序则是CDQ分治的基础。

[外链图片转存失败(img-UKxhfRtL-1568995946119)(https://endlesslethe.com/wordpress/wp-content/uploads/2019/09/mergesort4.jpg)]

如果我们考虑将数列二分，那么就需要考虑如上右图的两种情况——同侧和异侧：

• 当两个数在同侧时，在若干次分治之前，它们一定属于异侧
• 两个元素同侧时逆序对数已经在它们还是异侧时被计算过了，故不需要考虑同侧的元素之间的逆序对数，只需要处理两个数在异侧的情况

• 只需要处理异侧的情况，那么情况就变得简单：

  在合并左右两侧时，每次插入右侧的元素时，不妨计算左侧还未插入的元素的个数，它们都大于ai，其数量就是ai的逆序数。所以有 逆序数 = #左侧元素 - 插入后的pos(从0开始)

所以有结论：每次插入时，逆序数 = num - pos，num为左侧元素个数， pos为插入后的位置，从0开始数。

我们可以发现归并排序求逆序数的过程可以认为是符合CDQ分治思想的，我们在合并过程中计算左边区间对右边区间造成的影响——这就是CDQ分治，通过归并排序维护有序性，再通过左区间对右区间求解。

至于更多、更复杂的CDQ分治的问题与应用，读者可以自行阅读相关资料。

实现代码

void merger(int l, int r) {
    if(l == r) return ;
    int mid = (l + r) >> 1;
    merger(l, mid);
    merger(mid + 1, r);
    int pl = l, pr = mid + 1;
    for(int i=l; i<=r; i++) {
        if( (pl <= mid && a[pl] <= a[pr]) || pr > r ){
            b[i] = a[pl++];
        } else {
            b[i] = a[pr ++];
            ans += (mid - pl + 1);
        }
    }
    for(int i=l; i<=r; i++) a[i] = b[i];
           

归并树

回到这个熟悉的图：

[外链图片转存失败(img-yK4rkRj4-1568995946120)(https://endlesslethe.com/wordpress/wp-content/uploads/2019/09/mergesort4.jpg)]

从上图可以发现，归并排序的过程构成了一颗类似线段树的树。那么它支不支持区间查询呢？

区间查询>x的数

假如我们查询的是区间[a, b]中值 > x的个数？

显然我们对相关的不重叠区间分别进行一次二分查找就可以。一次二分查找需要时间\(O(logN)\)，而区间[a, b]至多被分为\(logN\)个不重叠的小区间，这样在\(O(log^2N)\)我们就得到了答案。

１. 建树

void init(int k, int l, int r) {	我们通过vector<int> dat[4*MAXN]的形式来储存数列。相当于线段树的每个节点不再储存一个值，而是一个数列。
    if (r-l == 1) dat[k].push_back(A[l]);
    else {	而merge函数是std提供的、将两个有序数列合并的库函数。
        init(ls, l, mid);
        init(rs, mid, r);
        dat[k].resize(r-l);
        merge(dat[ls].begin(), dat[ls].end(),
                     dat[rs].begin(), dat[rs].end(), dat[k].begin());
    }
}
           

２. 查询

int query(int a, int b, int x, int k, int l, int r) {//查询区间 [a,b)
    if (r <= a || b <= l) return 0;//区间不相交
    if (a <= l && r <= b) return upper_bound(dat[k].begin(), dat[k].end(), x) - dat[k].begin();
    else {
        int v1 = query(a, b, x, ls, l, mid);
        int v2 = query(a, b, x, rs, mid, r);
        return v1+v2;
    }
}
int qt(int a, int b, int x) {//封装query()函数
    return query(a, b, x, 0, 0, N);
}
           

区间查询第k大

换一个不那么显然的问题，查询区间第k大，题目表述如下：

Note：这是一个经典的题目，有很多解法可以使用。而且这个题目是求静态的数列，升级版还有动态的数列。其中最常见的解法是可持久化线段树（主席）和平方分割。（看不懂就划掉

看起来对于归并树来说，第k大数的查询涉及区间的合并问题，很难做。我们含泪在外层嵌套一个二分，先将问题转化为判定\(a_i\)是否是第k大。这里二分的意思就是说：首先计算中位数（即排序好后的数列b的中间那个数b[n/2]）在区间[i, j]是第几大，如果大于k，则取[mid+1, n]的中位数继续二分。（如果还没有看懂的话，那应该是没有二分的基础，建议先阅读参考文献IV"浅谈二分答案"。）

而现在的问题不就是变成计算小于中位数的元素个数了吗？！正好是上一个问题。所以要解决区间第K大的问题，只需要在上一个问题的基础上加一个二分就好了。限于篇幅，这里就不给出代码了。

时间复杂度

整体时间复杂度为\(O(nlogn+mlog^3n)\)。

建树的时间复杂度为\(O(nlogn)\)，然后m个查询，二分\(O(logn)\)加上查找区间的\(O(logn)\)，再加上在区间内部的二分\(O(logn)\)，这样在\(O(mlog^3n)\)我们就得到了答案。

归并树的应用

• 查询区间第K大

• 区域树（常见的方法是通过线段树套线段树完成区间查询）

  可以把之前“查询[a, b]中<v的点的个数”看成“查询a≤x≤b, y≤v的点的个数”

相关例题

• POJ 1804

  归并排序模板题

• POJ 2104

  区间第k大

参考文献

I. 白话经典算法系列之五 归并排序的实现

II. 归并排序求逆序对

III. 《挑战程序设计竞赛 第二版》

IV. 浅谈二分答案