为什么我的合并排序实现比冒泡排序和插入排序慢

Question

我试图比较不同排序算法在时间（时间执行）方面的复杂性。我比较了冒泡排序、插入排序、快速排序和融合排序（mergesort）。

我知道合并排序和快速排序比其他方法更快，但当我尝试比较这些方法的执行时间时，合并排序总是比其他方法花费更多的时间。我尝试了1000到10000个元素的列表。有人能告诉我为什么吗？

这是我的合并代码：

def inserer(element, ls):
   if  ls==[]:
       return [element]
   elif element<= ls[0]:
       return [element] + ls
   else:
       return [ls[0]] + inserer(element, ls[1:len(ls)])
def fusion(L1,L2):
   if L1==[]:
       return L2
   elif L2==[]:
       return L1
   else:
       return fusion(L1[1:len(L1)],inserer(L1[0], L2))

def triFusion (ls):
   n=len(ls)
   if n==0 or n==1:
       return ls
   else:
       return fusion(triFusion(ls[0:n//2]),triFusion(ls[n//2:n]))

Answer 1

我认为这里的问题是，您的合并（融合）函数的实现方式比需要的慢得多

def fusion(L1,L2):
   if L1==[]:
       return L2
   elif L2==[]:
       return L1
   else:
       return fusion(L1[1:len(L1)],inserer(L1[0], L2))

您的代码是通过重复获取L1的第一个元素，通过线性搜索将其插入L2，然后重复来实现的。这种方法的时间复杂度在最坏的情况下是O（n²），因为第一次插入可能必须扫描n个元素以找到元素的适当位置，第二次插入可能不得不扫描n+1、第三次n+2等。

这打破了通常使用mergesort时的时间界限。通常，合并操作需要花费时间O（n）。由于mergesort对原始数组的一半大小的数组进行两次递归调用，然后调用merge，因此mergesort的正常时间复杂度遵循以下递归：

T（n）=2T（n/2）+O（n）

其利用主定理求解为O（n-logn）。然而，在您的情况下，由于合并步骤需要时间O（n²），因此运行时为

T（n）=2T（n/2）+O（n²）

主定理称其解为O（n²）。换句话说，实现的时间复杂度是二次型的，就像冒泡排序和插入排序一样，但由于它对低效算法进行了大量调用，因此可能具有更高的常数因子。

若要解决此问题，请尝试将合并算法重写为在线性时间内运行。这可能会让你的代码运行得更快。