Mergesort in Python，我的第一个排序算法，出了什么问题？

Question

def mergesort(a): 
    if len(a)<=1: 
     return a 

    else: 
     mid=len(a)/2 
     mergesort(a[:mid]) 
     mergesort(a[mid:]) 
     auxa=[] 
     j=0 
     k=mid 
     while j<mid and k<len(a): 
      if a[j]<a[k]: 
       auxa.append(a[j]) 
       j+=1 
      else: 
       auxa.append(a[k]) 
       k+=1 

     if j==mid: 
      auxa.extend(a[k:]) 

     if k==len(a): 
      auxa.extend(a[j:mid]) 

     a=auxa 


     return a 

testlist=[3,2,1] 
print mergesort(testlist) 

结果我得到的是2 1 3

任何帮助非常感谢，谢谢！

Answer 1

您的函数mergesort返回一个新列表，并且不会修改您提供的列表，因为您似乎期望它正在执行。因此，例如，当您拨打mergesort(a[:mid])时，返回的是这些元素的新排序版本，而原始a[:mid]保持完全相同。

编辑：这里的问题是python列表切片工作的方式。当你说a[:mid]时，python会创建一个'copy'（我们不用担心原始文件的确切类型）。现在，当您在函数中修改此副本时，您所做的只是将其中的引用更改为指向新整数，而不是以任何方式修改原始副本。下面是一些代码以充实了这一点：

def change(a): 
    a[1] = 0 

a = [1, 2, 3] 
change(a) 
a 
>> [1, 0, 3] 

a = [1, 2, 3] 
change(a[:2]) 
a 
>> [1, 2, 3] 

编辑2：复制回（中发表的意见（abamert的建议））做正确的价值观：

def mergesort(a): 
    if len(a)<=1: 
    return a 

    else: 
    mid=len(a)/2 
    a = mergesort(a[:mid]) + mergesort(a[mid:]) 
    auxa=[] 
    j=0 
    k=mid 
    while j<mid and k<len(a): 
     if a[j]<a[k]: 
      auxa.append(a[j]) 
      j+=1 
     else: 
      auxa.append(a[k]) 
      k+=1 

    if j==mid: 
     auxa.extend(a[k:]) 

    if k==len(a): 
     auxa.extend(a[j:mid]) 


    return auxa 

这显然是更好的方式做这涉及到较少的复制，但我认为这个解决方案与原始代码的问题稍有关系。

Answer 2

这就是我想出了：

from collections import deque 

def mergesort(array): 
    if len(array) <= 1: return array 

    midpoint = len(array)/2 

    left_array = deque(mergesort(array[:midpoint])) 
    right_array = deque(mergesort(array[midpoint:])) 

    merged_array = deque([]) 

    while len(left_array) and len(right_array): 
     if left_array[0] < right_array[0]: 
      merged_array.append(left_array.popleft()) 
     else: 
      merged_array.append(right_array.popleft()) 

    merged_array.extend(left_array) 
    merged_array.extend(right_array) 

    return merged_array 

print mergesort([3, 2, 1])