归并排序算法模板

#include <bits/stdc++.h>
using namespace std;

long long invCount = 0;  // 逆序对数
int tmp[100010];

void mergeSort(int a[], int lo, int hi) {
    if (lo >= hi) return;
    int mid = lo + (hi - lo) / 2;
    mergeSort(a, lo, mid);
    mergeSort(a, mid + 1, hi);

    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) tmp[k++] = a[i++];
        else {
            tmp[k++] = a[j++];
            invCount += mid - i + 1;  // 求逆序对
        }
    }
    while (i <= mid) tmp[k++] = a[i++];
    while (j <= hi) tmp[k++] = a[j++];
    for (int i = lo; i <= hi; i++) a[i] = tmp[i];
}

int main() {
    int a[] = {5, 3, 8, 1, 2};
    mergeSort(a, 0, 4);
    for (int x : a) cout << x << " ";  // 1 2 3 5 8
    cout << endl << invCount << endl;   // 7
    return 0;
}

📖 要点说明

• 时间 O(n log n)，空间 O(n)
• 稳定排序：相等元素相对位置不变
• 合并时求逆序对：a[i] > a[j] 则 mid-i+1 个逆序

⚠️ 常见错误

• 临时数组忘拷贝回原数组
• 合并时 <= 写成 < 导致不稳定
• 逆序对计数时条件方向搞反