Невозможно объяснить, почему код не ведет себя так, как ожидалось, в простой цикл while

Question

Я пытаюсь реализовать алгоритм сортировки слияния в python. Я вставляю код (с отпечатками для отслеживания потока) и вывод того же самого. Как вы можете видеть, все работает правильно до окончательной операции слияния.

def mergesort(alist): 
if(len(alist) == 1): 
    return alist 
else: 
    mid = len(alist)/2 
    leftHalf = mergesort(alist[:mid]) 
    rightHalf = mergesort(alist[mid:]) 

    i, j, k = 0, 0, 0 #i= leftHalf counter, j= rightHalf counter, k= alist counter 

    while i < len(leftHalf) and j < len(rightHalf): 
     if(leftHalf[i] < rightHalf[j]): 
      alist[k] = leftHalf[j] 
      i += 1; k += 1 
     else: 
      alist[k] = rightHalf[j] 
      j += 1; k += 1 
     print "i=", i, "j=", j, "k=",k 
    print "quit the loop" 

    if(i<j): #it means j has proceeded ahead in its righthalf 
     remaining = leftHalf 
     r = i 
    else: 
     remaining = rightHalf 
     r = j 

    print remaining 
    print "k =",k 
    while (r < len(remaining)): 
     alist[k] = remaining[r] 
     r += 1; k += 1 

    print "i =", i , ";j = ", j,";k = ", k 
    print "alist sorted =", alist 
    print "*********" 
    return alist 

alist = [3,9,6,12,4,5] 
mergesort(alist) 
print alist 

Ниже трассировка для ввода alist = [3,9,6,12,4,5]

while условием, что говорит while i < len(leftHalf) and j < len(rightHalf): должна позволять 6 быть скопированы из leftHalf[1] в alist[3], верно? Я этого не вижу.

Если кто-то может объяснить, почему это не удается, то поместит меня из моих страданий :)

Answer 1

Вы ошибка здесь

if(leftHalf[i] < rightHalf[j]): 
    alist[k] = leftHalf[j] 
    i += 1; k += 1 
else: 
    alist[k] = rightHalf[j] 
    j += 1; k += 1 

вам не нужно leftHalf[j], но leftHalf[i] в alist[k] = leftHalf[j].