Алгоритм слияния Python

Question

Кажется, что это работает сейчас ... Открытая критика приветствуется. Ty trroten.

debug = 1 
#List to be merged 
A=[1,2,3,4,5,6,1,2,3,4,5,6,7] 

#Artificial variables from calling function 
p=0 
r=len(A) 
q=int(((p+r)/2)-1) 

#List to append merged values 
B=[] 

#End of list 
end=len(A) 

if debug: 
    print ('Mid: %d\n' % (q)) 
    print ('End: %d' % (end)) 

#Left and Right lists with sentinels 
L=A[:q+1] 
R=A[q+1:] 
L.append(None) 
R.append(None) 

#Init counters 
i=k=j=l=0 

if debug: 
    print ('A:%s' %(A)) 
    print ('\n') 
    print ('L:%s' %(L)) 
    print ('R:%s' %(R)) 
    print ('\n') 

#Merge Left and Right lists 
for k in A: 
    if debug: 
     print ('Iteration:%d' % (l)) 
     l+=1 
     print ('i=%d, j=%d' % (i, j)) 
     print ('B:%s' %(B)) 
     print ('\n') 
    if L[i] is not None and L[i]<=R[j]: 
     B.append(L[i]) 
     i+=1 
    else: 
     B.append(R[j]) 
     j+=1 

print ('Result:',B) 

Я пытаюсь написать алгоритм слияния в Python, но я продолжаю сталкиваться с этой ошибкой.

Traceback (most recent call last): 
    File "C:/Python34/Scripts/mergeSort.py", line 19, in <module> 
    if L[i]<=R[j] and i<mid: 
IndexError: list index out of range 

Я рассмотрел другие алгоритмы, но у них, похоже, нет той же проблемы. Пожалуйста помоги.

A=[2,4,5,7,1,3,7,8,9] 
B=[] 


end=len(A) 
mid=int(end/2) 

L=A[:mid] 
R=A[mid+1:] 

i=k=j=0 

for k in A: 
    if L[i]<=R[j] and i<mid: 
     B.append(L[i]) 
     i+=1 
    elif j<end: 
     B.append(R[j]) 
     j+=1 

print (B) 

Answer 1

Вы должны проверить, являются ли i и j inbounds перед вызовом этого индекса.

Answer 2

Ваш for цикл проходит через все пункты в A, длина которого превышает L или R. Итак, в какой-то момент i и j становятся больше, чем длина L и R. В этот момент ссылка L[i] или R[j] вызывает IndexError.