归并排序与逆序对

前言：分治——把大问题拆成小问题

假设你是班里的体育委员，要把全班 30 个人按身高排成一列。怎么排？

一种方法：把 30 个人分成两组，每组 15 人，分别排好队，然后合并——从两个已排好的队列中，每次挑出最矮的那个放到结果里。递归下去：15 人再分成 7 和 8……直到只剩 1 个人，天然有序。

这就是归并排序：把问题对半拆开，各自解决，再合并结果。“对半拆”保证深度只有 $\log n$ 层，“合并”每层总共扫 $n$ 个元素，所以总时间是 $O(n \log n)$。

和快速排序相比，归并排序多了一个”显式合并”的步骤，但换来的是稳定的性能保证——没有最坏情况，永远是 $O(n \log n)$。

这篇笔记还有第二个目的。归并过程中，左半和右半各自已经排好序了。这时候如果右半的某个元素比左半的某个元素小，它们就构成一个逆序对——一个在竞赛中频繁出现的计数问题。我们只需要在归并时顺手统计一下就行，不需要额外的算法。

归并排序与逆序对

问题的本质

快速排序是”先分区，再递归”，pivot 的位置在分区过程中才确定。归并排序反过来——先递归，再合并。把数组一分为二，各自排好序后，用 $O(n)$ 的归并操作合成整体有序。

$$T(n) = 2T(n/2) + O(n) \implies T(n) = O(n \log n)$$

和快排不同，归并排序的最坏、最好、平均都是 $O(n \log n)$——稳定可靠。

归并操作

两个有序数组合成一个有序数组，双指针线性扫描：

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

完整的归并排序

void mergesort(vector<int>& a, int l, int r, vector<int>& tmp) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergesort(a, l, mid, tmp);
    mergesort(a, mid + 1, r, tmp);
    merge(a, l, mid, r, tmp);
}

每次把区间对半分，递归到底（单个元素天然有序），然后逐层向上归并。需要一个辅助数组 tmp，空间 $O(n)$。

逆序对

逆序对：若 $i < j$ 且 $a[i] > a[j]$，则 $(i, j)$ 构成一个逆序对。

逆序对的数量衡量数组的”混乱程度”——已排序时为 0，完全逆序时为 $\binom{n}{2}$。

关键观察：归并时，左半和右半各自已经有序。当 a[j] < a[i]（右边的元素比左边小）时，a[i], a[i+1], ..., a[mid] 这 mid - i + 1 个元素都和 a[j] 构成逆序对——因为它们都比 a[j] 大，且下标都在 j 前面。

只需要在归并的比较分支中加一行计数：

long long merge_count(vector<int>& a, int l, int mid, int r, vector<int>& tmp) {
    long long cnt = 0;
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            cnt += mid - i + 1;  // a[i..mid] 都比 a[j] 大
            tmp[k++] = a[j++];
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    for (int i = l; i <= r; i++) a[i] = tmp[i];
    return cnt;
}

long long mergesort_count(vector<int>& a, int l, int r, vector<int>& tmp) {
    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    long long cnt = 0;
    cnt += mergesort_count(a, l, mid, tmp);
    cnt += mergesort_count(a, mid + 1, r, tmp);
    cnt += merge_count(a, l, mid, r, tmp);
    return cnt;
}

例题：逆序对计数

给定长度 $n$ 的数组，求逆序对个数。$1 \le n \le 5 \times 10^5$。

暴力 $O(n^2)$ 必然超时。归并排序过程中顺手计数，总时间 $O(n \log n)$。

#include <cstdio>
#include <vector>
using namespace std;

vector<int> a, tmp;

long long merge_count(int l, int mid, int r) {
    long long cnt = 0;
    int i = l, j = mid + 1, k = l;
    while (i <= mid && j <= r) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else { cnt += mid - i + 1; tmp[k++] = a[j++]; }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= r)   tmp[k++] = a[j++];
    for (int i = l; i <= r; i++) a[i] = tmp[i];
    return cnt;
}

long long solve(int l, int r) {
    if (l >= r) return 0;
    int mid = l + (r - l) / 2;
    long long cnt = 0;
    cnt += solve(l, mid);
    cnt += solve(mid + 1, r);
    cnt += merge_count(l, mid, r);
    return cnt;
}

int main() {
    int n;
    scanf("%d", &n);
    a.resize(n); tmp.resize(n);
    for (int i = 0; i < n; i++) scanf("%d", &a[i]);
    printf("%lld\n", solve(0, n - 1));
    return 0;
}

解析：逆序对分成三类——都在左半、都在右半、跨左右。前两类递归求解，跨左右的在归并时统计。因为左右各有序，a[j] < a[i] 时左半从 i 开始所有元素都与 a[j] 构成逆序对，一次加 mid - i + 1 即可。注意答案可能达到 $\binom{5 \times 10^5}{2} \approx 1.25 \times 10^{11}$，必须用 long long。