python - python 中的合并排序

Question

我是 python 的新手，正在尝试在 Python 中实现 merge_sort，这是我的代码。但它进入无限循环。谁能指出为什么？谢谢

def merge_sort(a):
    '''implement merge sort for array'''
    l = len(a)
    if l == 1:
        return a[0]
    a1 = merge_sort(a[:l/2-1])
    a2 = merge_sort(a[l/2:-1])
    a_sort = []
    idx1, idx2 = 0, 0
    #for i in range(l):
    if idx1 == len(a1):
        a_sort.append(a2[idx2:])
        import ipdb; ipdb.set_trace()
        return a_sort
    elif idx2 == len(a2):
        a_sort.append(a1[idx1:])
        return a_sort
    else:      
        if a1[idx1] >= a2[idx2]:
            a_sort.append(a2[idx2])
            idx2 += 1
        else:
            a_sort.append(a1[idx1])
            idx1 += 1

Answer 1

问题是当你的递归得到一个空列表时(即 l == 0)，你在返回任何东西之前调用了 merge_sort([]) 两次.您需要添加一个检查 if l == 0: return []。

此外，您对 if l == 1: return a[0] 的检查有点错误； merge_sort 应该总是返回一个列表，而这是返回一个列表元素(数字或字符串或其他)。所以它可能只是

if l <= 1:
    return a

此外，您的 a2 实际上不包含数组的最后一个元素:您需要 a[l/2:]，而不是 a[l/2:-1]。 (请记住，Python 中的范围不包括最后一个元素。)

这不影响代码的正确性，但是您应该使用l//2 表示整数除法；在 Python3 中，或者如果您执行 from __future__ import division，如果 l 为奇数，则 l/2 将是一个 float 。