迭代归并排序实现疑问：为何复杂度变为O(n²)而非O(nlogn)？

嘿，我来帮你理清这个问题～首先先给你吃个定心丸：你的代码逻辑是正确的，能输出正确的排序结果，但你对时间复杂度的分析犯了一个常见的错误，导致误以为它变成了O(n²)。

先澄清时间复杂度的误区 #

你认为while循环执行n-1次，每次最多耗时O(n)，所以总复杂度是O(n²)——这个推理的问题在于，你把每次合并的最坏情况耗时当成了平均情况，并且错误地累加了这些耗时。

实际上，归并排序的总耗时是由「所有合并操作中处理元素的总次数」决定的：

• 每个元素在整个排序过程中，会被合并log₂n次（因为每次合并后，它所在的子列表长度都会翻倍，直到最终成为整个列表）。
• 总共有n个元素，每个元素被处理log₂n次，所以总操作次数是n * log₂n，也就是标准的O(n log n)复杂度。

举个直观的例子，比如n=8：

• 第一层合并：4次合并单元素列表，每次处理2个元素，总处理量4×2=8
• 第二层合并：2次合并双元素列表，每次处理4个元素，总处理量2×4=8
• 第三层合并：1次合并四元素列表，处理8个元素，总处理量1×8=8
• 总处理量：8+8+8=24=8×3=8×log₂8，完美符合O(n log n)

你的while循环虽然执行了7次（n-1），但每次合并的耗时是逐步递增的，所有循环的耗时总和是线性增长的，绝非O(n²)。

关于代码的小优化（可选） #

你提到暂时忽略链表的问题，但还是要提一句：Python的list.pop(0)是O(k)时间复杂度（k为当前列表长度），因为数组结构需要移动后面所有元素来填补空位。如果想让merge函数真正达到O(n)的效率，可以改用collections.deque的popleft()方法（O(1)时间），修改后的merge函数会快很多：

from collections import deque

def merge(l, r):
    res = []
    l_deque = deque(l)
    r_deque = deque(r)
    while l_deque or r_deque:
        if not l_deque:
            res.extend(r_deque)
            break
        elif not r_deque:
            res.extend(l_deque)
            break
        else:
            if l_deque[0] <= r_deque[0]:
                res.append(l_deque.popleft())
            else:
                res.append(r_deque.popleft())
    return res

总结 #

你的迭代归并排序逻辑是正确的，时间复杂度依然是O(n log n)——之前的错误只是对复杂度的分析方式不对。如果优化一下pop(0)的实现，实际运行效率会更接近理论复杂度。

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