使用Python來表示合併排序，如何避免IndexError

Question

我知道這是不正確的，我發現another method沒有無限數量，但我仍然想知道它是否可以通過使用無限數字來糾正。

def MergeSort(A): 
    if len(A) > 1: 
     mid = len(A)/2 
     left = A[0:mid] 
     right = A[mid:] 

     MergeSort(left) 
     MergeSort(right) 

     w = float("inf") 
     left.append(w) 
     right.append(w) 
     i,j = 0,0 
     for k in range(len(A)): 
      if left[i] <= right[j]: 
       A[k] = left[i] 
       i += 1 
      else: 
       A[k] = right[j] 
       j += 1 

Answer 1

問題出在for k in range(len(A)):循環內;如果left中的所有值已用盡，但right（或反之亦然）中的值仍然存在，會發生什麼情況？

鏈接的方法增加了一個測試，基本上看起來像

if (left still has values) and ((right has no values) or (next_left < next_right)): 
    take a value from left 

你的代碼，而不是上方增加了一個安全值，以確保如果你是在左後衛的值可以保證比任何非更大警惕右值（反之亦然）。這是真的，直到for循環停止，其中左側和右側僅包含保護值。

另一個選項as seen here要循環，直到用盡左側或右側，然後有後續循環來收集其餘值。