Python中归并排序、插入排序与递归插入排序的运行时间对比及结果疑问解答

咱们一步步拆解问题根源：

1. 递归深度超限，程序根本没完成完整排序 #

Python默认的递归深度限制是1000左右（可以通过import sys; print(sys.getrecursionlimit())查看）。你的递归插入排序要处理50000个元素，需要连续递归调用50000次，这远远超过了默认限制，程序会直接抛出RecursionError: maximum recursion depth exceeded并终止。

你看到的0.068秒，根本不是完整排序的耗时——大概率是程序在崩溃前只执行了几百次递归调用就终止了，计时只统计了这极短的一小段时间，而非整个排序过程的真实开销。

2. 递归插入排序不可能比归并排序快，甚至跑不过普通插入排序 #

退一步说，就算你修改了递归深度限制让程序能跑完，递归版本的插入排序也绝对不可能出现比迭代插入排序更快、甚至超过归并排序的情况：

• 递归调用本身有额外的栈帧开销，每一次递归都要保存函数上下文，这会让它比纯迭代的插入排序更慢；
• 两者的时间复杂度都是O(n²)，对于50000个元素的随机列表，O(n²)意味着要做约2.5亿次比较/移动操作，而归并排序的O(nlogn)只需要约80万次操作，差距是几百倍，不可能出现递归插入排序更快的反常识结果。

为什么你会得到这个错误结果？ #

大概率是以下情况之一：

• 你的测试环境中临时修改了递归深度限制，但程序在排序完成前因为栈溢出（或内存问题）提前终止，计时只统计了终止前的部分时间；
• 你误将测试代码中的列表长度改小了（比如写成range(50)而非range(50000)）；
• 计时逻辑没有捕获异常，程序崩溃后依然输出了不完整的时间差。

修正测试的建议 #

如果想得到准确的测试结果，可以这么优化：

• 调整递归深度（谨慎使用）：如果一定要测试递归插入排序，先修改递归深度限制（注意：过大的递归深度可能导致栈溢出）：

  import sys
  sys.setrecursionlimit(100000)  # 调整到足够覆盖50000次递归的值
  

• 使用相同的测试数据：生成一次随机列表，用副本传给三个排序函数，避免数据随机性导致的误差：

  test_list = [random.randint(-10000, 10000) for i in range(50000)]
  
  t0 = time.time()
  insertion_sort(test_list.copy())
  t1 = time.time()
  
  try:
      recursive_insertion_sort(test_list.copy(), 50000)
      t2 = time.time()
      print("recursive insertion sort timer : ", t2 - t1)
  except RecursionError as e:
      print("Recursion depth exceeded! Can't complete recursive insertion sort.")
  
  merge_sort(test_list.copy())
  t3 = time.time()
  

• 多次测试取平均值：随机数据的分布会影响排序耗时，多次测试取平均能得到更可靠的结果。

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