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

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

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

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

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

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

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

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

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

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

以下が実装例です。

おわり。