Mergesort递归错误

Question

我编码这合并代码在python.The函数合并工作正常，当我单独调用它，它排序两个不同的排序lists.But当我在真正的合并排序递归问题中使用它时，它不做它的预期干活。我上传我的代码，请帮助我在这个问题

def merge(list,p,q,r): 

    list1=[] 
    list2=[] 
    list3=[] 
    i=0 
    j=0 
    for a in list[:q+1]: 
     list1.append(a) 
    list1.append(99999999999) 

    for b in list[q+1:]: 
     list2.append(b) 
    list2.append(9999999999999999999999999) 
    for k in range(len(list)): 
     if list1[i]<list2[j]: 
      list3.insert(k,list1[i]) 
      i=i+1 
     else: 
      list3.insert(k,list2[j]) 
      j=j+1 
     return list3 




def mergesort(list,p,r): 

    if p<r: 

     q=(p+r)/2 
     mergesort(list,p,q) 
     mergesort(list,q+1,r) 
     merge(list,p,q,r) 


list=[1,5,7,8,2,4,6,9] 

mergesort(list,0,7) 

print list 

有没有intendation错误

输出为：

[1, 5, 7, 8, 2, 4, 6, 9] 

其打印一样的列表 不选它

Answer 1

你是不是对矫正列表中选择功能“merge”

里面你要么需要修改list或return新list，你正在做既不

您可以从合并功能 返回项目list3和修改归并为：

def mergesort(list,p,r): 
    if p<r: 
     q=(p+r)/2 
     mergesort(list,p,q) 
     mergesort(list,q+1,r) 
     list =merge(list,p,q,r) 

嗨疯狂Ë它的工作： 使用

def merge(list,p,q,r): 

    list1=[] 
    list2=[] 
    list3=[] 
    i=0 
    j=0 
    for a in list[:q+1]: 
     list1.append(a) 
    list1.append(99999999999) 

    for b in list[q+1:]: 
     list2.append(b) 
    list2.append(9999999999999999999999999) 
    for k in range(len(list)): 
     if list1[i]<list2[j]: 
      list3.insert(k,list1[i]) 
      i=i+1 
     else: 
      list3.insert(k,list2[j]) 
      j=j+1 
    return list3 




def mergesort(list,p,r): 

    if p<r: 

     q=(p+r)/2 
     mergesort(list,p,q) 
     mergesort(list,q+1,r) 
     list = merge(list,p,q,r) 
     return list 

list=[1,5,7,8,2,4,6,9] 

list = mergesort(list,0,7) 

print list