为什么归并排序的合并步骤是O(n)，整体时间复杂度却不是O(n)？

归并排序时间复杂度疑问解答 #

你出现这个误解的核心原因是只统计了最后一轮合并的开销，漏掉了归并排序的每一层递归都要执行O(n)量级的合并操作，总时间复杂度为「递归层数」乘以「单层总开销」：

• 你给出的长度为8的Unsorted_Arr，归并排序会先递归拆分出log₂8 = 3层非叶子节点，每一层所有合并任务加起来遍历的元素总数都是固定的8，也就是单层总时间复杂度为O(n)：
  • 最底层（第一次合并）：将8个长度为1的元素两两合并，共4组合并任务，每组遍历2个元素，总遍历次数8
  • 中间层：将4个长度为2的有序子数组合并为2个长度为4的有序子数组，共2组合并任务，每组遍历4个元素，总遍历次数8
  • 最顶层（最后一轮合并）：就是你提到的将2个长度为4的子数组合并，总遍历次数8
• 3层总遍历次数为38=24，刚好符合nlog₂n的计算结果，扩展到任意长度为n的数组，总最坏时间复杂度就是O(n log n)
• 你提到的最后一轮合并只是其中1层的开销，不能代表整个排序过程的总开销。

内容的提问来源于stack exchange，提问作者rank1psysuck