Pythonで学ぶアルゴリズム 第20弾：並べ替え（マージソート） - Qiita

#Pythonで学ぶアルゴリズム< マージソート > はじめに 基本的なアルゴリズムをPythonで実装し，アルゴリズムの理解を深める． その第20弾としてマージソートを扱う． マージソート マージソートはまず，リストを順に半分ずつにしてバラバラにする．そのイメージ図を次に示す． 上図の最下層，つまりバラバラになったものを次は，逆に統合していく．このときに大きさを比較しながら統合していくことで，すべての要素が再構築されるときには並べ替えられた状態になっているという原理である．そのイメージ図を次に示す． 実装 再帰を使わずに実装を試みようとしたが，うまくいかなかったため，再帰を利用したコードとそのときの出力を以下に示す． コード """ 2021/01/22 @Yuya Shimizu マージソート：リストを半分ずつ分割 → 並べ替えしながら再構築 """ def merge_sort(da