递归合并排序无法正常工作

Question

我编写了一个应该执行递归合并排序的程序，我首先创建了一个fusion方法来使用索引合并两个列表

这里是fusion方法

def Fusion (L,d,f,m):
  aux=[]
  i_d=d
  i_m=m
  while (i_d<=m-1 and i_m<=f-1):
    if(L[i_d]<=L[i_m]):
        aux.append(L[i_d])
        i_d+=1
    else:
        aux.append(L[i_m])
        i_m+=1
  while (i_d<=m-1):
    aux.append(L[i_d])
    i_d+=1
  while (i_m<=f-1):
    aux.append(L[i_m])
    i_m+=1
  for j in range(len(aux)):
    L[j]=aux[j]

此方法工作正常，我使用两个排序列表对其进行了测试

这里的merge方法

 def sort_fusion(T,a,b):
  if (a<b):
    m=(a+b)//2
    sort_fusion(T,a,m) 
    sort_fusion(T,m+1,b)
    Fusion(T,a,b,m)  

运行程序

k1 =[3,1,0,9,1,2,6,8,5,7]
a=0
b=len(k1)
sort_fusion(k1,a,b)

程序将此[2, 5, 6, 6, 7, 8, 1, 8, 5, 7]作为输出，并提供此输入[3, 1, 0, 9, 1, 2, 6, 8, 5, 7]

我无法理解程序的行为，当我对sort_fusion(T,m+1,b)指令进行注释时，它会将这个[0, 1, 2, 3, 6, 8, 5, 7, 9, 1]作为输出，对我来说，当我跟踪它的进度时，算法很好

谁能指出问题所在吗

Answer 1

L[j]=aux[j]

这里，你可能需要

L[j + d] = aux[j]

原因是您从L中获取值，从索引d开始。当您将辅助数组写回L时，您希望将数字写回相同的位置