【基本情報技術者試験】マージソートをPythonで実装

今回はマージソートをPythonで実装します。

1. 基本交換法（バブルソート）
2. 基本選択法（選択ソート）
3. 基本挿入法（挿入ソート）
4. シェルソート
5. クイックソート
6. マージソート←今回の対象
7. ヒープソート

マージソートとは？

マージソートとは要素数が2以下になるまで半分に分割することを繰り返し、要素数が2以下になったらそのグループ内でソートする。全ての分割が完了したら、各グループ内の値を比較し並べ替えながら結合していくことで、全体の配列をソートしていくアルゴリズムです。
例えば8, 3, 1, 2, 7, 5, 6, 4という数列があったときに下記のように更新していきます。

① 8, 3, 1, 2 | 7, 5, 6, 4  （中央で分割する）
② 8, 3 | 1, 2 | 7, 5 | 6, 4 （左右のグループを更に分割する）
③ 3, 8 | 1, 2 | 5, 7 | 4, 6 （各グループ内でソートする）
④ 1, 2, 3, 8 | 4, 5, 6, 7 （ソートしながらマージしていく）
⑤ 1, 2, 3, 4, 5, 6, 7, 8 （ソートしながらマージしていく）

実際のPythonのコードは下記になります。

def merge(left, right):
  merged = []
  i, j = 0, 0

  # 左右のグループの値を比較して、小さい方の値をマージ後の配列に加える
  while (i < len(left)) and (j < len(right)):
    if left[i] <= right[j]:        
      merged.append(left[i]) 
      i += 1
    else:
      merged.append(right[j])
      j += 1

  # 残った方の要素は後ろにまとめて追加する
  if i < len(left):
    merged.extend(left[i:])     
  if j < len(right):
    merged.extend(right[j:]) 

  return merged

def mergesort(data):
  if len(data) == 2:
    return data if data[0] <= data[1] else [data[1], data[0]]
  if len(data) <= 1:
    return data

  mid = len(data) // 2 

  # 再帰的に分割
  left = mergesort(data[:mid])     
  right = mergesort(data[mid:])    

  #統合
  return merge(left, right)

listNum = [8, 3, 1, 2, 7, 5, 6, 4]

listNum

[8, 3, 1, 2, 7, 5, 6, 4]

mergesort(listNum)

[1, 2, 3, 4, 5, 6, 7, 8]

以上でマージソートの実装は終わりです。
次回はソートアルゴリズムの最後となるヒープアルゴリズムを実装します。