【Python】マージソート【アルゴリズム】

この記事は約1分で読めます。

マージソートについて

  • 計算量はO(nlogn)
  • 大容量のデータにも使える
  • リストの各要素を新しいリストとしてバラバラにした後で統合していく
  • 統合は2つのリストを使って行うことを繰り返す
  • 統合時は各リストの先頭の要素を大小比較し、小さい方を取り出すことを繰り返す

 

コード

[1]merge_sort関数

引数として受け取ったリストの要素数が1以下の場合はそのままリストを返します。[2]

リストの中央のインデックスをmidに代入します。[3]

中央から左のリストと中央から右側のリストに対して、同じことを繰り返します。[4]

merge関数を呼び出します。[5]

 

参考

こちらの書籍を参考にしています。

一度バラバラに分解してから統合していく様子を図にして解説しています。

また、左右に分割したリストについて、それぞれの先頭を比較して取り出す点についても触れられています。

どちらも、直感的にわかりやすい説明になっているので、チェックしてみるとより理解が深まるかと思います。

コメント