python3.4.3中的Mergesort不起作用；对于NoneTyp，typeerror

Question

我目前正在尝试一个用于排序和合并列表的代码，但无法使用：

def mergesort(L):
    """Returns a new sorted list with the same elements as L"""
    print (L)
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L) / 2)
        left = mergesort(L[:middle])
        right = mergesort(L[middle:])
        together = merge(left,right)
        print( 'merged', together)
        return

事情就是这样：

>>> test = [1, 3, 5, 6, 4, 7, 20, 9]
>>> mergesort(test)
[1, 3, 5, 6, 4, 7, 20, 9]
[1, 3, 5, 6]
[1, 3]
[1]
[3]
merged [1, 3]
[5, 6]
[5]
[6]
merged [5, 6]
Traceback (most recent call last):
  File "<pyshell#347>", line 1, in <module>
    mergesort(test)
  File "C:/Python27/python omg 2 samma/lec10.py", line 30, in mergesort
    left = mergesort(L[:middle])
  File "C:/Python27/python omg 2 samma/lec10.py", line 32, in mergesort
    together = merge(left,right)
  File "C:/Python27/python omg 2 samma/lec10.py", line 7, in merge
    while i < len(left) and j < len(right):
TypeError: object of type 'NoneType' has no len()

似乎左右两个变量没有被正确保存，因为如果我写这个，我会得到更好的结果，尽管结果仍然是错误的（改变了我写“在一起”的方式）：

def mergesort(L):
    """Returns a new sorted list with the same elements as L"""
    print (L)
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L) / 2)
        left = mergesort(L[:middle])
        right = mergesort(L[middle:])
        together = merge(mergesort(L[:middle]),mergesort(L[middle:]))
        print( 'merged', together)
        return

我得到：

>>> test = [1, 3, 5, 6, 4, 7, 20, 9]
>>> mergesort(test)
[1, 3, 5, 6, 4, 7, 20, 9]
[1, 3, 5, 6]
[1, 3]
[1]
[3]
[1]
[3]
merged
[1, 3]
[5, 6]
[5]
[6]
[5]
[6]
merged [5, 6]
[1, 3]
[1]
[3]
[1]
[3]
merged [1, 3]
[5, 6]
[5]
[6]
[5]
[6]
merged [5, 6]
Traceback (most recent call last):
   File "<pyshell#349>", line 1, in <module>
     mergesort(test)
   File "C:/Python27/python omg 2 samma/lec10.py", line 30, in mergesort
     left = mergesort(L[:middle])
   File "C:/Python27/python omg 2 samma/lec10.py", line 32, in mergesort
     together = merge(mergesort(L[:middle]),mergesort(L[middle:]))
   File "C:/Python27/python omg 2 samma/lec10.py", line 7, in merge
     while i < len(left) and j < len(right):
TypeError: object of type 'NoneType' has no len()

Answer 1

您的mergesort()返回None，除非L的长度小于2。您还需要返回together：

def mergesort(L):
    """Returns a new sorted list with the same elements as L"""
    print (L)
    if len(L) < 2:
        return L[:]
    else:
        middle = int(len(L) / 2)
        left = mergesort(L[:middle])
        right = mergesort(L[middle:])
        together = merge(left,right)
        print( 'merged', together)
        return together

如果不这样做，left或right最终被设置为None，如果L[:middle]长于1，并且merge()调用失败。你知道吗

此固定版本随后产生：

>>> mergesort(test)
[1, 3, 5, 6, 4, 7, 20, 9]
[1, 3, 5, 6]
[1, 3]
[1]
[3]
merged [1, 3]
[5, 6]
[5]
[6]
merged [5, 6]
merged [1, 3, 5, 6]
[4, 7, 20, 9]
[4, 7]
[4]
[7]
merged [4, 7]
[20, 9]
[20]
[9]
merged [9, 20]
merged [4, 7, 9, 20]
merged [1, 3, 4, 5, 6, 7, 9, 20]
[1, 3, 4, 5, 6, 7, 9, 20]