1. 概述
归并排序（Merge Sort）是经典的排序算法之一，其核心思想是 分治（Divide and Conquer）。通过将问题拆解为多个子问题，分别求解后再将结果合并，最终得到完整的解。
在本文中，我们将重点分析归并排序的时间复杂度（Big O 表示法），并探讨哪些输入数据组合会导致其进入最坏运行状态。
2. 归并排序的两个核心步骤
归并排序的执行过程可以分为两个阶段：
✅ 步骤一：拆分（Divide）
此阶段会不断将数组一分为二，直到每个子数组只包含一个元素。例如，一个包含 16 个元素的数组，其拆分过程如下：
对于长度为 n 的数组，其拆分的总次数为 n/2 + n/4 + ... + 1，总和为 n - 1。因此，该阶段的时间复杂度为 **O(n)**。
✅ 步骤二：合并与排序（Merge + Sort）
这是归并排序的关键部分。在合并过程中，两个已排序的子数组会被合并成一个有序数组。最终，整个数组完成排序：
每次合并操作的时间复杂度为 **O(n)**，而整个合并过程会进行 log n 次，因此该阶段的时间复杂度为 **O(n × log n)**。
✅ 总体时间复杂度
归并排序的总时间复杂度为两个阶段的叠加，即：
✅ O(n) + O(n × log n) = O(n × log n)
这个时间复杂度不仅适用于平均情况，也是归并排序的最坏情况。
3. 归并排序的最坏情况
归并排序的性能与输入数据的顺序密切相关。在合并过程中，若左右两个子数组中的元素 交替出现在最终排序结果中，则会触发最多的比较操作，从而导致最坏性能。
❗举例说明
假设左右子数组分别为：
left = {1, 3, 5, 7};
right = {2, 4, 6, 8};
在合并这两个子数组时，每个元素都需要被比较至少一次，无法提前终止比较过程。这种情况下，归并排序的运行效率最低。
🔍 最坏输入组合示例
对数组 {1,2,3,4,5,6,7,8} 来说，输入顺序为 {5,1,7,3,6,2,8,4} 将触发最坏情况：
在这种情况下，每次合并操作都会触发最大数量的比较和移动操作，导致整体运行时间最长。
🧠 总结关键点
| 条件 | 是否触发最坏情况 |
|---|---|
| 左右子数组元素交替出现 | ✅ 是 |
| 左右子数组高度有序 | ❌ 否 |
| 左右子数组完全无序 | ❌ 否 |
| 所有元素都相同 | ❌ 否 |
4. 结论
归并排序的时间复杂度为 **O(n × log n)**，无论输入数据如何分布，其最坏情况的时间复杂度都不会超过这一上限。
最坏情况发生在每次合并操作中，左右子数组的元素交替出现在最终排序结果中。这种情况下会导致最多的比较操作，从而拖慢整体排序效率。
对于需要稳定排序且数据量较大的场景，归并排序依然是一个非常可靠的选择。但在实际开发中，了解最坏情况有助于我们更合理地评估其性能表现。