無法編寫合併代碼

Question

我已經使用Sedgewick在課程中教授的算法，在Python中編寫了Mergesort的實現。我無法正確分類。代碼有什麼問題？

def merge(a, aux, lo, mid, hi): 
    assert isSorted(a, lo, mid) 
    assert isSorted(a, mid+1, hi) 

    for k in range(lo, hi): 
     aux[k] = a[k] 

    i = lo 
    j = mid + 1 
    for k in range(lo, hi): 
     if i > mid: 
      a[k] = aux[j] 
      j += 1 
     elif j > hi: 
      a[k] = aux[i] 
      i += 1 
     elif a[i] < a[j]: 
      a[k] = aux[i] 
      i += 1 
     else: 
      a[k] = aux[j] 
      j += 1 
    assert isSorted(a, lo, hi) 

def sort(a, aux, lo, hi): 
    if (lo >= hi): return a 
    mid = math.floor(lo + (hi-lo)/2) 

    sort(a, aux, lo, mid) 
    sort(a, aux, mid+1, hi) 
    merge(a, aux, lo, mid, hi) 

def merge_sort(a): 
    aux = [0] * len(a) 
    sort(a, aux, 0, len(a)) 
    assert isSortedArray(a) 

Answer 1

Python使用基於0的索引。您需要將您的lo，mid，hi調整爲基於0的索引。

起點是

sort(a,aux,0, len(a)-1)