python之python 中的合并排序

我是 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 

请您参考如下方法:

问题是当你的递归得到一个空列表时(即 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 。