归并排序通过“分而治之”将数组递归拆分为最小单元后，再逐层合并有序子数组。分解阶段持续二分直至单元素为止；合并阶段利用双指针比较两子数组首元素，较小者入结果数组，直至所有元素合并完毕。其时间复杂度恒为O(n log n)，空间复杂度为O(n)。该算法稳定高效，适用于链表与外部排序，实现需注意边界控制与临时数组管理。
归并排序的核心思想是“分而治之”。它通过将一个大数组不断拆分成两个小数组，分别排序后再合并，最终得到有序的整体。整个过程分为两个阶段：分解和合并。
分解：递归拆分数组
把待排序的数组从中间一分为二，形成左右两个子数组。然后对这两个子数组继续递归地拆分，直到每个子数组只剩下一个元素或为空——单个元素天然有序，这是递归的终止条件。
例如，数组 [38, 27, 43, 3, 9, 82, 10] 会逐步拆成最小单位。
合并：有序子数组合并
合并阶段是归并排序的关键。两个已经排好序的子数组，可以通过比较它们的首元素，依次取出较小的放入新数组，完成有序合并。
立即学习“Python免费学习笔记（深入）”；
具体操作方式：
- 准备两个指针，分别指向两个子数组的开头
- 比较当前指针所指元素，将较小的加入结果数组，并移动对应指针
- 重复上述过程，直到一个子数组遍历完
- 将另一个子数组剩余元素全部追加到结果中
时间与空间特性
归并排序的时间复杂度稳定为 O(n log n)，无论最好、最坏还是平均情况都一样。因为它总是将数组对半分（log n 层），每层合并操作总共处理 n 个元素。
缺点是需要额外的存储空间来存放临时合并结果，空间复杂度为 O(n)，不适合内存受限的场景。
基本上就这些。归并排序稳定且高效，特别适合处理链表排序或外部排序问题。实现起来逻辑清晰，关键是理解递归拆分和有序合并的过程。不复杂但容易忽略细节，比如边界控制和临时数组管理。
