归并排序（Merge Sort）

归并排序是一种分治算法。它将一个大数组分成两个小数组，分别递归地排序，然后将两个有序数组合并成一个有序数组。

核心三步骤（分治三部曲）：

分（Divide）：找到中点，将数组分成左右两半。
治（Conquer）：递归地对左右两半进行归并排序。
合（Combine）：将两个已排序的子数组合并成一个有序数组。

关键词：稳定排序、分治、额外空间 O(n)、时间复杂度稳定 O(n log n)。

算法步骤（以升序为例）

假设要对数组 arr[l..r] 进行排序：

终止条件：l >= r，即子数组长度 ≤ 1，已经有序，直接返回。
分解：mid = (l + r) / 2
递归左半：mergeSort(arr, l, mid)
递归右半：mergeSort(arr, mid+1, r)
合并：将 arr[l..mid] 和 arr[mid+1..r] 合并成一个有序数组，放回 arr[l..r]。

合并过程（关键操作）

合并两个有序数组需要临时数组辅助。

合并算法流程（双指针）：

i 指向左半起始位置 l
j 指向右半起始位置 mid+1
k 指向临时数组起始位置 0

while i <= mid and j <= r:
    if arr[i] <= arr[j]:
        tmp[k++] = arr[i++]
    else:
        tmp[k++] = arr[j++]

while i <= mid:  # 左半剩余
    tmp[k++] = arr[i++]
while j <= r:    # 右半剩余
    tmp[k++] = arr[j++]

将 tmp[0..k-1] 拷贝回 arr[l..r]

代码实现

经典版本（递归 + 临时数组）

#include <iostream>
using namespace std;

int tmp[100010];  // 全局临时数组，避免递归中反复分配

void mergeSort(int arr[], int l, int r) {
    if (l >= r) return;          // 边界：只有一个元素或空
    int mid = (l + r) / 2;
    mergeSort(arr, l, mid);      // 排序左半
    mergeSort(arr, mid + 1, r);  // 排序右半

    // 合并 [l, mid] 和 [mid+1, r]
    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j])
            tmp[k++] = arr[i++];
        else
            tmp[k++] = arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= r)   tmp[k++] = arr[j++];

    // 拷贝回原数组
    for (i = l, k = 0; i <= r; ++i, ++k)
        arr[i] = tmp[k];
}

int main() {
    int arr[] = {5, 3, 8, 6, 2, 7, 1, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    mergeSort(arr, 0, n - 1);
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    return 0;
}

复杂度分析

复杂度	值	说明
时间复杂度（最好）	$O(n \log n)$	每次划分均匀
时间复杂度（最坏）	$O(n \log n)$	总是划分均匀，无退化
时间复杂度（平均）	$O(n \log n)$	稳定
空间复杂度	$O(n)$	需要辅助数组（可优化到 $O(1)$ 但复杂且不稳定）
稳定性	稳定	合并时相等元素优先取左边

推导：
递推公式 $T(n) = 2T(n/2) + O(n)$ ，根据主定理 $T(n) = O(n \log n)$ 。

归并排序的特点

优点

稳定：相等元素的相对顺序不变（对结构体排序有用）。
最坏情况也是 O(n log n)：不像快速排序可能退化为 $O(n^2)$ 。
适合链表排序：链表归并只需 $O(1)$ 额外空间。
适合外部排序：可以分块读入内存排序后合并（如大文件排序）。

缺点

需要额外 O(n) 空间：不如快速排序、堆排序节省空间（原地排序）。
递归深度 $O(\log n)$ ：但栈空间相比额外数组可忽略。
常数因子较大：比快速排序慢一些（平均情况下）。

应用场景

求逆序对数量
在合并两个有序子数组时，若右半当前元素 arr[j] < arr[i]，则左半从 i 到 mid 的所有元素都大于 arr[j]，即产生 (mid - i + 1) 个逆序对。 代码片段（在合并过程中累加）：

   long long cnt = 0;
   // 在 while(i<=mid && j<=r) 中：
   if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
   else {
       tmp[k++] = arr[j++];
       cnt += (mid - i + 1);   // 关键：统计逆序对
   }

大文件外部排序
将大文件分成多个小块，每块排序后写入临时文件，再多路归并。
链表排序
链表归并排序是 O(n log n) 且空间 O(1) 的经典方法。
稳定排序需求
当排序稳定性很重要时（如先按成绩排序，再按学号排序需要稳定算法）。

归并排序 vs 快速排序

特性	归并排序	快速排序
时间复杂度（平均）	$O(n \log n)$	$O(n \log n)$
时间复杂度（最坏）	$O(n \log n)$	$O(n^2)$ （可优化为随机化）
空间复杂度	$O(n)$ 额外空间	$O(\log n)$ 递归栈（原地划分）
稳定性	稳定	不稳定（常规实现）
适用场景	稳定排序、外部排序、链表排序	内存内排序、期望速度快
常数因子	较大	较小

竞赛建议：

如果题目对稳定性无特殊要求，且数组规模大，一般用 sort（快速排序/内省排序）。
如果需要求逆序对，或实现稳定排序，或对链表排序，用归并排序。

常见考题变式

求逆序对
求重要逆序对（i < j 且 a[i] > 2*a[j]）
计算右侧小于当前元素的个数
合并 K 个有序链表（分治归并）。
使用归并排序求数组中的小和（每个元素左边比它小的元素之和）。