最大递归深度达到合并排序

我一直在尝试实现合并排序，但我一直运行到“Maximum Recursion Depth”错误。我目前的理论是，“如果listlen < = 1：”不抓住它，但我想不出为什么最大递归深度达到合并排序

def mergesort(listin): 
    listlen = len(listin) 

    if listlen <= 1: 
     return listin 

    left = [] 
    right = [] 
    i = 0 
    while i < listlen: 
     if i <= listlen/2: 
      left.append(listin[i]) 
     else: 
      right.append(listin[i]) 
     i += 1 

    left = mergesort(left) 
    right = mergesort(right) 


    return merge(left, right) 

def merge(listlef, listrig): 
    result = [] 

    while len(listlef) != 0 and len(listrig) != 0: 
     if listlef[0] <= listrig[0]: 
      result.append(listlef[0]) 
      listlef = listlef[1:] 
     else: 
      result.append(listrig[0]) 
      listrig = listrig[1:] 

    while len(listlef) != 0: 
     result.append(listlef[0]) 
     listlef = listlef[1:] 
    while len(listrig) != 0: 
     result.append(listrig[0]) 
     listrig = listrig[1:] 

    return result

来源

2017-02-07 user3800750

也许不相关的，但如果你是使用python 3，'listlen/2'返回一个浮点数。您必须执行'//'（适用于所有python版本） –

如果您有足够长的输入，则最大递归错误是不可避免的。 – chepner

忘记补充说，这发生在低至2个数字 – user3800750

对于大小为2的列表，请注意i只会是0和1，这两者都是小于或等于2/1 == 1

，而不是与指数摆弄，虽然只是替代它列出你追加到：

left = [] 
right = [] 
for item in listin: 
    left.append(item) 
    left, right = right, left

来源

2017-02-07 21:31:13 chepner

我会假装我想指出这种技术，而不是仅仅忽视评论中提到的明显解决方案。 – chepner

最大递归深度达到合并排序

回答

相关问题