IndexError: список индексов вне диапазона на операции

Question

слиянием Я получаю эту ошибку:

Traceback (most recent call last): 
    File "Lab1.py", line 24, in <module> 
    b = mergesort(a) 
    File "Lab1.py", line 19, in mergesort 
    left = mergesort(lst[:middle]) 
    File "Lab1.py", line 21, in mergesort 
    return merge(left, right) 
    File "Lab1.py", line 12, in merge 
    result.append(right[j]) 
IndexError: list index out of range 

... на этот код:

def merge(left, right): 
    result = [] 
    i, j = 0, 0 
    while i < len(left) and j < len(right): 
     if left[i] <= right[j]: 
      result.append(left[i]) 
      i += 1 
     else: 
      j += 1 
    result.append(right[j]) 
    return result 

def mergesort(lst): 
    if len(lst) <= 1: 
     return lst 
    middle = int(len(lst)/2) 
    left = mergesort(lst[:middle]) 
    right = mergesort(lst[middle:]) 
    return merge(left, right) 

a = [3,1,2,5,9,6,7] 
b = mergesort(a) 
print('Input #1: ' + ', '.join(str(x) for x in a)) 
print('Output #1: ' + ', '.join(str(x) for x in b)) 

Я использую Python 3.3.2.

Answer 1

Вы добавляете 1 в j в цикл while; если j = len(right) - 1 вы закончите с j = len(right), и это недействительный индекс; индексы к спискам must осень в диапазоне [0, length) (так 0 в комплекте, lengthисключая).

Дозапись перед тем приращением j, в петле, и продлить результат с остатком (которые уже отсортированный):

def merge(left, right): 
    result = [] 
    i, j = 0, 0 
    while i < len(left) and j < len(right): 
     if left[i] <= right[j]: 
      result.append(left[i]) 
      i += 1 
     else: 
      result.append(right[j]) 
      j += 1 
    result.extend(left[i:]) 
    result.extend(right[j:]) 
    return result 

Ломтики никогда не поднимать IndexError; если индексы выпадают за пределы доступных значений, возвращаются пустые списки. По крайней мере один из left[i:] и right[j:] будет пустым.

Демо:

>>> a = [3,1,2,5,9,6,7] 
>>> b = mergesort(a) 
>>> print('Input #1: ' + ', '.join(str(x) for x in a)) 
Input #1: 3, 1, 2, 5, 9, 6, 7 
>>> print('Output #1: ' + ', '.join(str(x) for x in b)) 
Output #1: 1, 2, 3, 5, 6, 7, 9