归并排序（Merge Sort）是一种基于分治法的高效且稳定的排序算法。它的工作原理是将输入数组分成两半，递归地对它们进行排序，然后使用一个名为 merge() 的函数将这两个有序的半部分合并在一起。
核心函数 INLINECODE44ad6ceb 假定 INLINECODE2b0b2cfb（左半部分）和 arr[m+1..r]（右半部分）这两个部分已经是有序的，并将它们合并成一个有序数组。
归并排序是如何工作的
让我们通过以下步骤来拆解这个过程：
- 分解：递归地将数组分成两半，直到每个子数组只包含一个元素。
- 解决：分别对每个子数组进行排序（如果子数组只包含一个元素，则它本身就已经是有序的）。
- 合并：将有序的子数组按正确的顺序合并成一个单一的有序数组。
归并排序图解
假设我们要使用归并排序对数组或列表 [38, 27, 43, 10] 进行排序。
让我们来看看上述示例的具体工作流程：
分解阶段：
- [38, 27, 43, 10] 被分为 [38, 27] 和 [43, 10] 。
- [38, 27] 被分为 [38] 和 [27] 。
- [43, 10] 被分为 [43] 和 [10] 。
解决阶段：
- [38] 已经是有序的。
- [27] 已经是有序的。
- [43] 已经是有序的。
- [10] 已经是有序的。
合并阶段：
- 合并 [38] 和 [27] 得到 [27, 38] 。
- 合并 [43] 和 [10] 得到 [10, 43] 。
- 合并 [27, 38] 和 [10, 43] 得到最终的有序列表 [10, 27, 38, 43] 。
因此，排序后的列表是 [10, 27, 38, 43]。
Python 代码实现
Python
CODEBLOCK_1a0aaccb
输出结果
Given array is: [12, 11, 13, 5, 6, 7]
Sorted array is: [5, 6, 7, 11, 12, 13]
代码原理解析：
分解：
- 在 INLINECODE88246ab9 中，INLINECODEf078d9e0 条件确保只有当数组包含多于一个元素时才进行分解。
- 中间点计算为
m = l + (r - l) // 2。 - 通过递归调用将数组分为两半：
mergeSort(arr, l, m) → 对左半部分进行排序。
mergeSort(arr, m + 1, r) → 对右半部分进行排序。
解决：
- 每个递归调用持续进行分解，直到子数组仅包含单个元素（此时自动有序）。
- 一旦分解完成，递归开始返回——在每一层级，两个有序的半部分都准备好进行合并。
合并：
merge(arr, l, m, r)函数负责将两个有序的半部分合并。- INLINECODEcdee7bcf 和 INLINECODE8adfa3c0 分别计算左右子数组的大小。
- 使用循环将元素复制到临时数组 INLINECODE90539ecf 和 INLINECODE772a7a89 中。
- 变量 INLINECODE4bcf1e60、INLINECODEe58f8738 和
k分别初始化为左数组、右数组和合并数组的索引。 - 循环 INLINECODE085ed7cf 会比较 INLINECODE825ef60b 和 INLINECODE0d0479e1，将较小的元素放入 INLINECODE89dcec19。
- 当其中一个列表的元素耗尽后，INLINECODE1abb1ab4 或 INLINECODE1c2d0953 中剩余的元素会被复制回
arr。 - 这种合并过程会递归地持续进行，直到整个数组变为有序。
归并排序的优点
- 对于大型数据集非常高效。
- 保证 O(n log n) 的时间复杂度性能。
- 稳定的排序算法（保留相等元素的原始顺序）。
- 非常适用于链表数据结构。
缺点
- 需要额外的辅助空间（空间复杂度为 O(n)）。
- 对于小型数据集，相比插入排序等简单算法，速度较慢。
相关文章：
> – 快速排序
> – 插入排序算法