Python中list.sort()与list.sort(key=itemgetter(0))性能差异疑问

嘿，作为刚接触Python刷LeetCode的新手，你观察得真细致！这个问题其实挺值得深究的，咱们一步步来拆解清楚：

1. 两种排序方式理论上是否等价？ #

先明确两个排序逻辑的区别：

• intervals.sort()：Python中列表的默认排序是字典序排序——当元素是子列表时，会先比较子列表的第一个元素；如果第一个元素相等，会继续比较第二个元素，以此类推。
• intervals.sort(key=itemgetter(0))：明确指定只按每个子列表的第一个元素进行排序，完全忽略后面的元素。

对于「合并重叠区间」这个问题来说，两种排序方式最终得到的结果是满足需求等价的——因为我们只需要区间按左端点有序，就能正确完成合并。哪怕第一个元素相同的区间，不管它们的右端点顺序如何，合并后的结果都是一样的。

不过严格来说，两种排序的输出列表不完全相同：当存在左端点相同的区间时，默认排序会把右端点小的区间放在前面，而itemgetter(0)排序会保留这些区间原来的相对顺序（因为Python的sort是稳定排序，键相同的元素不会改变原有顺序）。但这种差异完全不影响合并结果。

2. 为什么性能会有差异？ #

你看到的80ms vs 110ms的差异，主要来自两个原因：

• 排序逻辑的开销不同：itemgetter(0)是operator模块中用C实现的函数，它的开销比Python默认的字典序比较要小。默认排序在比较子列表时，只要第一个元素相等，就会继续比较第二个元素——哪怕我们根本不需要这一步。当测试用例中存在大量左端点相同的区间时，这种额外的比较会累积成明显的耗时差异。
• LeetCode计时的波动：虽然服务器的负载、同一时段的提交量等因素会导致单次计时有波动，但你这里的差异已经足够明显，核心原因还是两种排序方式本身的性能差异，而非单纯的计时误差。

3. 可以自己验证的小实验 #

你可以本地运行下面的代码，直观感受两种排序的耗时差异：

from operator import itemgetter
import time

# 构造测试用例：10万左端点相同、右端点乱序的区间
intervals = [[5, i] for i in range(100000, 0, -1)]

# 测试itemgetter(0)排序
start = time.time()
copy1 = intervals.copy()
copy1.sort(key=itemgetter(0))
print(f"itemgetter(0) 耗时: {time.time() - start:.4f} 秒")

# 测试默认排序
start = time.time()
copy2 = intervals.copy()
copy2.sort()
print(f"默认sort 耗时: {time.time() - start:.4f} 秒")

运行后你会发现，默认排序的耗时明显更高——因为它要逐个比较右端点，而itemgetter(0)完全跳过了这一步。

总结 #

• 对于你的问题场景，两种排序方式都能满足合并需求，但严格来说排序结果不完全相同（不影响最终合并结果）；
• 性能差异主要是因为默认排序做了额外的比较操作，而itemgetter(0)是更高效的C实现；
• LeetCode的计时有波动，但你看到的差异核心是排序方式本身的性能差距。

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