为何合并M个已排序数组的时间复杂度为线性时间？

嘿，咱们先从你提到的外部排序场景入手，先纠正一个常见的误解：单个元素不需要和其他块的所有元素比较——这正是合并过程能高效完成的关键！

先澄清你的误解 #

你之前觉得“每个元素需与其他块的所有元素比较，单个元素的比较次数为O(M)”，这其实是对归并方式的错误理解。如果真这么做，总时间会是O(nM)，那效率就太低了，完全不是线性的。实际合并M个有序数组（或者外部排序里的已排序块）时，我们用的是**优先队列（最小堆/最大堆）**来优化比较过程。

结合外部排序场景的正确合并过程 #

假设我们有M个已排序块，每个块k个元素，总元素数n=Mk：

• 初始化堆：把每个块的第一个元素放入一个大小为M的堆中（堆顶是当前所有元素里的最小值/最大值），这一步的时间复杂度是O(M)。
• 迭代提取与插入：
  1. 每次从堆顶取出当前最小的元素，将其加入最终的有序序列。
  2. 如果这个元素所在的块还有剩余元素，就把块里的下一个元素插入堆中。
  3. 每个堆的插入/提取操作的时间复杂度是O(logM)，我们总共要执行n次这样的操作（因为总共有n个元素要处理）。

时间复杂度的计算 #

总时间复杂度是初始化堆的O(M)加上n次堆操作的O(nlogM)，也就是O(nlogM)。那为什么会有人说是“线性时间”呢？

• 当M是一个常数时（比如外部排序中，内存能容纳的块数M固定不变），logM就是一个常数项，此时总时间复杂度可以简化为O(n)，也就是线性时间。
• 另外，在一些语境下，人们会把“相对于总元素数n的线性”称为线性时间，而logM作为一个增长缓慢的项，在n很大时对整体复杂度的影响远小于n的线性增长。

补充：二路归并的情况 #

如果不用堆，而是用经典的二路归并（每次合并两个有序块），那总共需要log₂M轮合并，每轮合并的时间都是O(n)（因为每轮要处理所有n个元素），总时间也是O(nlogM)，和堆方法的复杂度一致。

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