【Python】マージソートを実装してみた

Pythonでマージソートを実装してみました。

マージソートはソートの中で高速ですが、他のソートに比べて少し実装が難しいです。

しかし1つ1つステップを踏んで作ればそんなに難しくありません。

まずはマージソートの中身を順番に解説していきます。

  1.  整列されていないリストを2つのサブリストに分割する
  2. 分割したリスト(サブリスト)をマージソートを使って整列させる。(再帰関数)
  3. 2つのサブリストをマージして1つの整列済みリストにする

次に2つのサブリストをマージする手順をみていきます。

  1. AとBの先頭の数字を比較し、小さい方をCに追加し追加した値はリストから削除する
  2. 手順1をどちらか一方のリストが空になるまで繰り返す。
  3. 残った要素をCの末尾に追加する

以上のステップをそのまま実装すればマージソートは完成ですが、せっかくなので実際の例をみてみましょう。

そのほうがイメージがわきやすいと思います。

1. 整列前のリストです
[5,4,6,1,2,7,3]
2. 半分に分割します。
[5, 4, 6, 1] [2, 7, 3] 
3. 左側をさらに半分に分割
[5, 4] [6, 1]
4. それぞれ整列させる
[5] [4]
[6] [1]
5. 右側も半分に分割
[2, 7] [3]
6. それぞれ整列させる
[2] [7]
7. 最後にマージして完成!
[1, 2, 3, 4, 5, 6, 7]

以下が実装例です。

def MergeSort(num_list):
  n = len(num_list)
  
  if len(num_list) == 1:
    return num_list
  
  #1. 整列されていないリストを2つのサブリストに分割する
  mid = int(round(n/2))
  
  left = num_list[:mid]
  right = num_list[mid:]
  
  print(left,right)
  
  #2. 分割したリスト(サブリスト)を整列する。サブリストもマージソートを使って整列させる。(再帰関数)
  l = MergeSort(left)
  r = MergeSort(right)
  
  #3. 2つのサブリストをマージして1つの整列済みリストにする
  return Merge(l,r)
  
# 整列済みリストA、Bを使って、整列済みリストCを作成する
def Merge(A,B):
  C = []
#   print("A",A)
#   print("B",B)
  
  # 1. AとBの先頭の数字を比較し、小さい方をCに追加し追加した値はリストから削除する
  # 2. 手順1をどちらか一方のリストが空になるまで繰り返す。
  while (len(A) > 0) and (len(B) > 0):
    if A[0] < B[0]:
      C.append(A[0])
      del A[0]
    else:
      C.append(B[0])
      del B[0]
  
  # 3. 残った要素をCの末尾に追加する
  if len(A) > 0:
    C.extend(A)
  else:
    C.extend(B)

#   print("C",C)
  return C

おわり。