算法概述

归并排序（Merge Sort）是一种基于分治思想的稳定排序算法，由约翰·冯·诺依曼于 1945 年提出。它将数组递归地分成两半，分别排序，再将两个有序子数组合并成一个有序数组。

归并排序是外部排序（处理无法全部装入内存的大文件）的基石，也是许多稳定排序需求的默认选择。

核心思想

1. 分（Divide）：将当前数组从中间分成两个子数组，直到每个子数组只剩下一个元素（单个元素自然有序）。
2. 治（Conquer）：递归地对两个子数组进行归并排序。
3. 合（Combine）：将两个已排序的子数组合并（Merge）成一个有序数组。

归并排序的"归并"二字即来源于合并两个有序序列这一核心操作。

与快速排序的区别：

• 快速排序是"先分区，后递归"——分区操作在递归之前完成。
• 归并排序是"先递归到底，再回溯合并"——合并操作在递归返回时完成，是典型的后序遍历。

算法步骤 / 伪代码

合并两个有序子数组

function merge(arr, left, mid, right):
    // 创建两个临时数组存放左右子数组
    n1 = mid - left + 1
    n2 = right - mid
    L = arr[left .. mid]
    R = arr[mid+1 .. right]

    i = 0, j = 0, k = left
    while i < n1 and j < n2:
        if L[i] <= R[j]:
            arr[k] = L[i];  i++
        else:
            arr[k] = R[j];  j++
        k++

    // 将剩余元素复制回原数组
    while i < n1:  arr[k++] = L[i++]
    while j < n2:  arr[k++] = R[j++]

整体递归流程

function mergeSort(arr, left, right):
    if left < right:
        mid = (left + right) / 2
        mergeSort(arr, left, mid)       // 排序左半部分
        mergeSort(arr, mid + 1, right)  // 排序右半部分
        merge(arr, left, mid, right)    // 合并两个有序部分

C++ 代码实现

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

// 合并两个已排序的子数组 arr[left..mid] 和 arr[mid+1..right]
void merge(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;  // 左子数组长度
    int n2 = right - mid;     // 右子数组长度

    // 创建临时数组
    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];

    // 合并两个有序数组
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            arr[k++] = R[j++];
        }
    }
    // 复制剩余元素
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];
}

// 归并排序递归函数
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;  // 防止溢出
        mergeSort(arr, left, mid);            // 排序左半部分
        mergeSort(arr, mid + 1, right);       // 排序右半部分
        merge(arr, left, mid, right);         // 合并两个有序部分
    }
}

// ============ 应用：计算数组中的逆序对（LeetCode 剑指 Offer 51）============

// 在归并过程中统计逆序对
long long mergeAndCount(vector<int>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    vector<int> L(n1), R(n2);
    for (int i = 0; i < n1; ++i) L[i] = arr[left + i];
    for (int j = 0; j < n2; ++j) R[j] = arr[mid + 1 + j];

    long long invCount = 0;
    int i = 0, j = 0, k = left;

    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k++] = L[i++];
        } else {
            // L[i] > R[j]：L 中从 i 到 n1-1 的所有元素都与 R[j] 构成逆序对
            arr[k++] = R[j++];
            invCount += (n1 - i);
        }
    }
    while (i < n1) arr[k++] = L[i++];
    while (j < n2) arr[k++] = R[j++];

    return invCount;
}

// 归并排序的同时统计逆序对
long long mergeSortAndCount(vector<int>& arr, int left, int right) {
    long long invCount = 0;
    if (left < right) {
        int mid = left + (right - left) / 2;
        invCount += mergeSortAndCount(arr, left, mid);
        invCount += mergeSortAndCount(arr, mid + 1, right);
        invCount += mergeAndCount(arr, left, mid, right);
    }
    return invCount;
}

int reversePairs(vector<int>& nums) {
    vector<int> temp = nums; // 复制一份，避免修改原数组
    return (int)mergeSortAndCount(temp, 0, temp.size() - 1);
}

// ============ 主函数 ============
int main() {
    // ========== 测试归并排序 ==========
    vector<int> arr = {12, 11, 13, 5, 6, 7, 3, 9, 8, 1};
    cout << "排序前: ";
    for (int x : arr) cout << x << " ";
    cout << endl;

    mergeSort(arr, 0, arr.size() - 1);

    cout << "排序后: ";
    for (int x : arr) cout << x << " ";
    cout << endl;

    // ========== 测试逆序对（剑指 Offer 51）==========
    vector<int> nums1 = {7, 5, 6, 4};
    cout << "\n数组: ";
    for (int x : nums1) cout << x << " ";
    cout << endl;
    cout << "逆序对数量: " << reversePairs(nums1) << " (期望: 5)" << endl;

    vector<int> nums2 = {1, 3, 2, 3, 1};
    cout << "数组: ";
    for (int x : nums2) cout << x << " ";
    cout << endl;
    cout << "逆序对数量: " << reversePairs(nums2) << " (期望: 4)" << endl;

    return 0;
}

复杂度分析

指标	所有情况
时间	O(n log n)
空间	O(n)
稳定性	✅ 稳定

• 时间复杂度：无论最好、最坏还是平均情况，归并排序的时间复杂度都是 O(n log n)。递归树共有 log n 层，每一层合并操作的代价为 O(n)。

• 空间复杂度：O(n)。合并时需要额外的临时数组来存放两个子数组，这是归并排序的主要缺点。不过也有一些原地归并的实现方式（如块归并），但通常会影响时间效率。

• 稳定性：归并排序是稳定的。在合并两个有序子数组时，如果两个元素相等，我们会优先取左边子数组的元素（L[i] <= R[j] 时取 L[i]），从而保持了相等元素的原始相对顺序。

应用场景

1. 需要稳定排序的场景：当排序的对象有多个字段，需要先按一个字段排序再按另一个字段排序时，稳定性很重要。归并排序是许多语言中稳定排序的首选。

2. 外部排序：当数据太大无法全部装入内存时，可以采用多路归并的方式对磁盘上的大文件进行排序。核心思想就是分段排序后反复归并。

3. 链表排序：归并排序非常适合链表的排序，因为链表可以在 O(1) 时间内找到中间节点（快慢指针），且合并两个有序链表不需要额外空间。

4. 求逆序对：归并排序在合并过程中可以优雅地统计逆序对数量（见经典例题），这是归并排序的经典应用。

5. 计数问题：利用归并过程，还可以高效解决诸如"右侧小于当前元素的个数"（LeetCode 315）等问题。

经典例题

剑指 Offer 51 / LeetCode 面试题51 — 数组中的逆序对

题目描述：在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例：

输入: [7,5,6,4]
输出: 5
解释: 逆序对为 (7,5), (7,6), (7,4), (5,4), (6,4)

归并排序解法思路：

1. 利用归并排序的分治框架，在合并两个有序子数组时统计逆序对。
2. 假设左右两个子数组 L 和 R 都已经有序。当合并时，如果发现 L[i] > R[j]，由于 L 是有序的，L 中从 i 到末尾的所有元素都大于 R[j]，因此新增 n1 - i 个逆序对。
3. 最终逆序对总数 = 左半部分的逆序对 + 右半部分的逆序对 + 合并过程中发现的跨部分逆序对。

（完整 C++ 代码已包含在上方的代码实现中）