快速排序 归并排序 插入排序 选择排序

归并排序：先拆分，再合并

目标：理解归并排序的核心流程——把大问题拆小，再把两个有序段合并成更大的有序段。

绿色 = 左半段 蓝色 = 右半段 橙色 = 本轮合并结果

第一屏：原始数组

第二屏：课堂 mergeSort 代码（Java）

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

public static void merge(int[] a, int lo, int mid, int hi, int[] temp) {
    int i = lo, j = mid + 1, k = lo;
    while (i <= mid && j <= hi) {
        if (a[i] <= a[j]) temp[k++] = a[i++];
        else temp[k++] = a[j++];
    }
    while (i <= mid) temp[k++] = a[i++];
    while (j <= hi) temp[k++] = a[j++];
    for (int p = lo; p <= hi; p++) a[p] = temp[p];
}

第三屏：归并排序原理（通俗版）

归并排序可以理解为“分而治之”：先把数组不停对半拆开，再把已经有序的小段按顺序拼回来。

第 1 步：不断对半拆分 直到每段只剩 1 个元素，拆分阶段结束。
第 2 步：从最小段开始合并 每次都合并两个“已经有序”的段。
第 3 步：双指针比较 左右各放一个指针，谁小就先放进临时数组。
第 4 步：回写原数组 合并结果写回原数组对应区间，继续向上层返回。

一句话记忆：先拆到不能再拆，再把两个有序段“按小到大”合并回去。

第四屏：归并排序的特点（重点）

时间复杂度很稳定 最好、平均、最坏都为 O(n log n)，不会像快排那样退化到 O(n²)。
稳定排序 相等元素在排序后相对顺序不变，适合“主键 + 次键”场景。
空间复杂度 O(n) 需要临时数组辅助合并，所以经典写法不是原地排序。
适合大数据和链表 顺序读写友好，在外部排序、链表排序中常见。

结论：归并排序的最大优势是“性能稳定 + 稳定性好”，主要代价是“额外内存”。

第五屏：拆分递归树（先拆分）

mergeSort(0,7)
├─ mergeSort(0,3)
│  ├─ mergeSort(0,1)
│  │  ├─ mergeSort(0,0) 结束
│  │  └─ mergeSort(1,1) 结束
│  └─ mergeSort(2,3)
│     ├─ mergeSort(2,2) 结束
│     └─ mergeSort(3,3) 结束
└─ mergeSort(4,7)
   ├─ mergeSort(4,5)
   │  ├─ mergeSort(4,4) 结束
   │  └─ mergeSort(5,5) 结束
   └─ mergeSort(6,7)
      ├─ mergeSort(6,6) 结束
      └─ mergeSort(7,7) 结束

第六屏：7 次 merge 全貌 + 逐步细节

先看全貌，再看细节。每一次都按“全局数组（merge 前）→ 局部合并 → 回写后的全局数组”展示。

第七屏：最终结果 + 记忆要点

最终有序数组

3 条记忆要点