归并排序是基于“分而治之”（Divide and Conquer）思想的经典排序算法，非常适合初学者理解分治策略与递归的结合。它通过将复杂问题拆解为简单子问题，解决后再合并结果，最终实现高效排序。
一、分治思想：从“大问题”到“小问题”¶
“分治”的核心是 “分而治之”：将一个大问题拆分成多个小问题，逐个解决后，再将结果合并。
举个生活例子：整理一堆杂乱的扑克牌。
1. 分：把52张牌分成两堆（26张），再把每堆分成更小的两堆（13张），直到每堆只剩1张（天然有序）。
2. 治：将最小的牌堆（1张）按大小合并成两堆（2张），再合并成4张、8张……最终合并成完整的有序牌堆。
类比到数组排序：将数组分成两半，递归排序每一半，最后合并成一个有序数组。
二、归并排序的核心步骤¶
归并排序分为 “分解（Divide）” 和 “合并（Merge）” 两步：
1. 分解（Divide）：递归拆分数组¶
- 如果数组长度 ≤ 1，直接返回（单个元素已有序）。
- 否则，找到数组中间位置
mid，拆分为左半部分left和右半部分right。 - 递归分解左半部分和右半部分，直到子数组长度为1。
示例：数组 [5, 3, 8, 6, 2, 7, 1, 4]
- 第一次分解：中间位置 mid = 3，拆分为 left = [5,3,8,6] 和 right = [2,7,1,4]。
- 递归分解 left 和 right，直到所有子数组长度为1：[5], [3], [8], [6], [2], [7], [1], [4]。
2. 合并（Merge）：合并有序子数组¶
当子数组分解到长度为1后，开始合并相邻的有序子数组。合并时需确保结果有序：
- 用两个指针 i 和 j 分别指向两个子数组的起始位置。
- 比较 i 和 j 指向的元素，将较小的元素放入临时数组，移动对应指针。
- 重复直到一个子数组遍历完毕，将剩余元素直接放入临时数组。
- 最后将临时数组复制回原数组。
合并过程示例：
合并 [5] 和 [3]：
- 指针 i=0（指向 5），j=0（指向 3）。
- 比较：3 < 5，放入临时数组 → [3]，j=1（右子数组遍历完毕）。
- 剩余元素 [5] 直接放入 → 临时数组 [3,5]，复制回原数组，得到 [3,5]。
三、归并排序完整流程（以数组 [5,3,8,6,2,7,1,4] 为例）¶
- 分解：递归拆分为 8 个长度为1的子数组。
- 合并第一层：两两合并，得到 4 个有序子数组：
[3,5],[6,8],[2,7],[1,4]。 - 合并第二层：继续合并，得到 2 个有序子数组：
[3,5,6,8],[1,2,4,7]。 - 合并最终层：合并上述两数组，得到完整有序数组
[1,2,3,4,5,6,7,8]。
四、时间复杂度与空间复杂度¶
- 时间复杂度：分解的递归深度为
O(log n)（每次分解规模减半），每层合并需遍历所有元素（O(n)），总时间复杂度为O(n log n)（无论数组初始顺序如何，时间复杂度稳定）。 - 空间复杂度：合并过程需临时数组存储结果，额外空间为
O(n)。
五、稳定性：归并排序的优势¶
归并排序是 稳定排序：合并时若两个子数组出现相等元素（如 [2,2]），会优先取左边子数组的元素，不改变相等元素的相对顺序。
总结¶
归并排序通过“分治”思想将复杂排序问题简化为子问题，核心是 “分解-递归-合并”。它直观体现了如何将大问题拆解为可解决的小问题，是理解分治算法的绝佳案例。尽管需要额外空间，但时间复杂度稳定在 O(n log n)，适合处理大数据量或需要稳定排序的场景。
归并排序的原理清晰、步骤明确，通过本文的示例和讲解，相信你已能轻松掌握它的核心逻辑！