归并排序核心思路
一句话总结
归并排序的核心思路需要结合 二叉树的后序遍历 来理解：先利用递归把左右两半子数组排好序，然后在后序位置合并两个有序数组。
核心要点
1. 归并排序的核心思想
归并排序采用分治算法思想，结合二叉树的后序遍历：
先递归地将左右两半子数组排好序，然后在后序位置合并两个有序数组。
算法框架（概念性描述）：
1. 分解：将数组分成左右两半
2. 解决：递归地对左右两半进行排序
3. 合并：在后序位置合并两个已排序的子数组
2. 与快速排序的对比
| 维度 | 快速排序 | 归并排序 |
|---|---|---|
| 遍历模式 | 二叉树前序遍历 | 二叉树后序遍历 |
| 核心思路 | 先将一个元素放到正确位置，再递归处理左右 | 先递归处理左右，再合并结果 |
| 分区方式 | partition：选择一个 pivot，将数组分为两部分 | merge：合并两个已排序的子数组 |
| 思维难度 | 较易理解（从单个元素出发） | 需要理解递归和后续合并 |
3. 前置知识要求
学习归并排序需要掌握：
- 二叉树的遍历：理解前序、中序、后序遍历的概念
- 递归思维：归并排序是典型的递归算法
- 双指针技巧：用于合并两个有序数组
基本原理
归并排序的三步走
- 分解：找到数组中点，将数组分为左右两半
- 递归：对左右两半分别调用归并排序
- 合并：将两个已排序的子数组合并成一个有序数组
合并两个有序数组
归并排序的核心操作是 merge，使用双指针技巧：
- 指针 i 指向左子数组的起始位置
- 指针 j 指向右子数组的起始位置
- 比较 nums[i] 和 nums[j]，将较小的放入结果数组
- 重复直到所有元素都被处理
时间复杂度
| 情况 | 时间复杂度 | 说明 |
|---|---|---|
| 最好情况 | O(n log n) | 每次均匀分割数组 |
| 平均情况 | O(n log n) | 递归深度 log n，每层合并 O(n) |
| 最坏情况 | O(n log n) | 归并排序的时间复杂度稳定，不会出现最坏情况 |
归并排序的时间复杂度稳定在 O(n log n)，不像快速排序可能出现 O(n²) 的最坏情况。
空间复杂度
| 实现方式 | 空间复杂度 | 说明 |
|---|---|---|
| 递归实现 | O(n) | 需要额外的数组空间进行合并操作 |
| 递归栈 | O(log n) | 递归调用的深度 |
归并排序不是原地排序算法，需要 O(n) 的额外空间。
排序稳定性
归并排序是稳定排序。
原因：在合并两个有序数组时，如果遇到相等元素，可以先取左子数组的元素，保持原有相对顺序。
相关概念
- 排序算法：归并排序是 O(n log n) 排序算法的代表之一
- 快速排序：对比算法，采用前序遍历思维
- 二叉树：归并排序的思维模式来源（后序遍历）
- 递归：归并排序的实现方式
- 分治算法：归并排序的核心思想
- 双指针技巧：合并两个有序数组的关键技巧
- 后序遍历：二叉树遍历方式，归并排序的递归结构类似后序遍历
相关实体
- labuladong：本文作者，算法学习平台创作者
总结
归并排序是计算机思维的典型代表：通过分治思想 + 后序遍历，实现稳定的 O(n log n) 排序。与快速排序的"前序思维"不同，归并排序采用"后序思维"——先处理子问题，再合并结果。掌握归并排序需要理解递归、后序遍历和双指针合并技巧。
待补充
由于原文 markdown 提取不完整（defuddle 只提取了约 2KB，而原始 HTML 有 230KB），以下内容缺失：
- 完整的算法可视化说明
- 可能存在的代码示例（原文提到"具体的代码实现和算法运用会安排在二叉树章节后面"）
- 可能的常见错误和注意事项
- 可能的应用场景和变种算法
如需完整内容，建议手动复制原文或使用浏览器插件保存完整内容后重新摄取。