単純なループでコードが期待どおりに動作しない理由を特定できない

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 i < len(leftHalf) and j < len(rightHalf):6がalist[3]にleftHalf[1]からコピーできるようにする必要がありますと言うwhile条件のトレースのですか？私はこれが起こっているのを見ない。

これが失敗する理由を誰かが説明できるならば、それは私の悲惨さから私を出してあげる:)

Answer 1

あなたの間違いは、あなたがleftHalf[j]が、alist[k] = leftHalf[j]でleftHalf[i]必要はありませんここに

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

です。