Mergesortアルゴリズム（Python）の再帰的な動作はどうですか？

Question

は、ここに私のコード（のpython 2.7）である：

def merge_sort(a_list): 
    print ("Splitting ", a_list) 
    if len(a_list) > 1: 
     mid = len(a_list) // 2 
     left_half = a_list[:mid] 
     #print left_half 
     right_half = a_list[mid:] 
     #print right_half 
     merge_sort(left_half) 
     merge_sort(right_half) 

     i = 0 
     j = 0 
     k = 0 


     print ("Left half is ", left_half) 
     print ("Right half is ", right_half) 
     while i < len(left_half) and j < len(right_half): 

      if left_half[i] < right_half[j]: 
       a_list[k] = left_half[i] 
       i = i + 1 
      else: 
       a_list[k] = right_half[j] 
       j = j + 1 
      k = k + 1 

     while i < len(left_half): 
      a_list[k] = left_half[i] 
      i = i + 1 
      k = k + 1 

     while j < len(right_half): 
      a_list[k] = right_half[j] 
      j = j + 1 
      k = k + 1 

    print("Merging ", a_list) 



    a_list = [54, 26, 93, 17] 
    merge_sort(a_list) 
    print(a_list) 

そして、次のように私の出力は次のようになります。

`1.('Splitting ', [54, 26, 93, 17]) 
2.('Splitting ', [54, 26]) 
3.('Splitting ', [54]) 
4.('Merging ', [54]) 
5.('Splitting ', [26]) 
6.('Merging ', [26]) 
7.('Left half is ', [54]) 
8.('Right half is ', [26]) 
9.('Merging ', [26, 54]) 
10.('Splitting ', [93, 17]) 
11.('Splitting ', [93]) 
12.('Merging ', [93]) 
13.('Splitting ', [17]) 
14.('Merging ', [17]) 
15('Left half is ', [93]) 
16.('Right half is ', [17]) 
17.('Merging ', [17, 93]) 
18.('Left half is ', [26, 54]) 
19.('Right half is ', [17, 93]) 
20.('Merging ', [17, 26, 54, 93]) 
21.[17, 26, 54, 93]` 

私は何をして苦労することは私にはわからないということですなぜ出力の18行で左半分が突然[26,54]になります。私はそれが再帰的であることを知っているので、そうするべきです[54,26]？右半分は[93,17]でなければなりませんか？（行19の出力）

誰もが考えていますか？どうもありがとうございます！

Answer 1

それは再帰的だという事実は全く番号の順序には影響しません

...私はそれが再帰的である知っているので、それはする必要があります。内部ロジックは

[54,26]ですか？

いいえ。あなたのロジックは、昇順

# add the left half (the smaller number) to the merged list 
if left_half[i] < right_half[j]: 
    a_list[k] = left_half[i] 
    i = i + 1 
    else: # the right half is smaller, so add it 
     a_list[k] = right_half[j] 
     j = j + 1 

左半分が急になった[26,54]に数字を命じました。

突然ではありません。再帰的メソッド呼び出しは、呼び出しスタックを戻しました。