MergeSort出現問題

Question

def merge(L, start_index, sublist_size): 
    """ 
    Merge two sublists of a list L 

    Parameters: 
    L - the list 
    start_index - the index of the first element to be merged 
    sublist_size - the size of the chunks to be merged 

    Left chunk: L[start_index] to L[start_index + sublist_size - 1] 
    Right chunk: L[start_index + sublist_size] to L[start_index + 2 * sublist_size - 1] 
    """ 

    index_left = start_index 
    left_stop_index = start_index + sublist_size 
    index_right = start_index + sublist_size 
    right_stop_index = min(start_index + 2 * sublist_size, 
          len(L)) 

    print('Merging sublists:', L[index_left:left_stop_index], 'and', 
      L[index_right:right_stop_index]); 

    L_tmp = [] 

    while (index_left < left_stop_index and 
      index_right < right_stop_index): 
     if L[index_left] < L[index_right]: 
      L_tmp.append(L[index_left]) 
      index_left += 1 
     else: 
      L_tmp.append(L[index_right]) 
      index_right += 1 

    if index_left < left_stop_index: 
      L_tmp.extend(L[index_left : left_stop_index]) 
    if index_right < right_stop_index: 
      L_tmp.extend(L[index_right : right_stop_index]) 

    L[start_index : right_stop_index] = L_tmp 
    print('Merged sublist:', L_tmp, '\n') 

def merge_sort(L): 
    """ 
    Sort a list L using the merge sort algorithm. 

    (Starter code doesn't fully sort the list.) 
    """ 
    left_start_index = 0 
    chunksize = 1 # Start by dividing the list into N sub-lists of 1 element each 

    while chunksize < len(L):`enter code here` 
     print("\n*** Sorting sublists of size", chunksize) 
     print(L) 

     while left_start_index + chunksize < len(L): 
      merge(L, left_start_index, chunksize) 

      # Move to next pair of chunks 
      left_start_index += 2 * chunksize 

     chunksize= chunksize *2 
     print('List is now',L) 

嘿傢伙有很多困難完成此代碼。代碼的def merge部分很好，但是我遇到的問題是def_merge排序部分。因此，當第一次排序大小爲1的子列表時，代碼工作正常，但是我無法讓代碼繼續合併排序。我覺得問題存在於累加器中。

Answer 1

在merge_sort功能，運行內部while循環後，left_start_index值已更改爲不0，因此你的代碼不能正確排序合併超越該列表中的前兩個元素。在內部while循環之後，在chunksize=chunksize*2之前，重置left_start_index=0應該解決問題。

def merge_sort(L): 
    ... 
    #outer while loop 
    while chunksize < len(L): 
     .... 
     #inner while loop 
     while left_start_index + chunksize < len(L): 
      merge(L, left_start_index, chunksize) 

      # Move to next pair of chunks 
      left_start_index += 2 * chunksize 
     #Reset left_start_index to 0 
     left_start_index = 0 
     chunksize= chunksize *2 
     print('List is now',L)