归并排序 (Merge Sort)

基于分治（Divide and Conquer）策略的经典 $O(N \log N)$ 稳定排序算法

📖 算法原理：分、治、合

归并排序由冯·诺伊曼于 1945 年发明，是分治策略（Divide and Conquer）的完美体现：

  1. 分 (Divide)：将当前区间 $[L, R]$ 划分为左右两个子区间，直到区间长度退化为 1。
  2. 治 (Conquer)：递归对左右两个子区间分别进行归并排序。
  3. 合 (Combine)：使用双指针，将两个已排序的子区间交替比较，合并为一个有序的完整大区间。

🧠 NOI 必考时空复杂度断言

  • 时间复杂度：无论原数组是完全乱序、升序还是逆序，归并排序的递归树结构完全固定，其比较次数高度一致，时间复杂度稳定为 $O(N \log N)$。
  • 空间复杂度：在“合 (Merge)”的过程中，我们需要开辟一个外部的临时数组来暂存合并后的有序数据，因此空间复杂度为 $O(N)$。它属于非原地排序。
  • 稳定性：若遇到两个相等的数，双指针默认先复制左边侧子区间的元素，从而保证了相同元素的相对物理顺序不变，故属于稳定排序。
点击"自动播放"或"单步演练"观察分治递归树拆分与双指针合并过程
Level 0:
Level 1:
Level 2:
Level 3:
📥 临时合并区辅助数组 tmp[L..R] (Conquer & Merge Space) 
// 归并排序核心分治代码
void merge(int a[], int l, int mid, int r) {
    int i = l, j = mid + 1, k = 0;
    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 p = 0; p < k; p++) a[l + p] = tmp[p];
}

void mergeSort(int a[], int l, int r) {
    if (l >= r) return;
    int mid = l + (r - l) / 2;
    mergeSort(a, l, mid);     // 递归划分左子区间
    mergeSort(a, mid + 1, r); // 递归划分右子区间
    merge(a, l, mid, r);      // 运行双指针合并
}
📋 算法执行步骤历史