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部分は、問題のあるimがdef_mergeのsort部分であるためうまくいきます。サイズのサブリストをソートするときに初めてコードがうまく動作しますが、その後にマージソートを続けるコードを取得できません。あたかも問題がアキュムレータにあるかのように感じます。

Answer 1

merge_sort関数では、inner whileループを実行した後、left_start_indexの値が0に変更されています。そのため、コードはソートをリストの最初の2つの要素を超えて正しくマージできませんでした。内部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)