Максимальная глубина рекурсии достигнута Слияние Сортировка

Question

Я пытаюсь реализовать сортировку слияния, но я продолжаю работать с ошибкой «Максимальная погрешность рекурсии». Моя текущая теория гласит, что «если 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 

Answer 1

Для списка размера 2, обратите внимание, что i будет только 0 и 1, оба из которых меньше или равна 2/1 == 1.

Вместо возился с индексами, хотя, только альтернативный список, который вы добавляете к:

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