STEP 1.2 マージソート(merge sort) Pythonの例

解答例

[プログラム解答例]

import random

def merge(a1, a2): # pythonらしく、配列(Pythonのリスト)を変数にし、戻り値を使用する
   i, j = 0,0
   m, n = len(a1),len(a2)
   b = []  # bはマージした結果の配列 (Pythonのリスト)

   while i < m and j < n:
      if a1[i] < a2[j]:
          b.append(a1[i])
          i += 1;
      else:
          b.append(a2[j])
          j += 1;
   return b + a1[i:] + a2[j:] # マージした配列(Pythonのリスト)そのものをreturn


def merge_sort(array):   # ソート結果をreturnする関数とする
   if (len(array)) <= 1:
       return array   # 1つしかないとき、あるいは[]のときは、そのままで戻り値
   half = len(array) //2
   left = array[:half]
   right = array[half:]
   return(merge(merge_sort(left), merge_sort(right))) # 2つをマージした配列が戻り値


a = [random.randint(0,100) for i in range(10)] # 乱数で10個生成
print("before = {}".format(a))
print("after  = {}".format(merge_sort(a)))


実行例

[tsuchiya@www python]$ python3 merge_sort.py
before = [2, 77, 65, 52, 89, 27, 89, 24, 42, 47]
after  = [2, 24, 27, 42, 47, 52, 65, 77, 89, 89]