マージソート

merge-sort.png

マージソートは、まずは配列を半分に分けてからやるソートにゃ

マージソートは分割統治法に従って構成されたアルゴリズムの代表例である。

分割 ソートすべき長さnの列を2つの長さn/2の部分列に分割する
統治 マージソートを用いて2つの部分列を再帰的にソートする
統合 2つのソートされた部分列をマージしてソートされた解を作る

再帰が底をつくのは
ソートすべき列の長さが1になった時である。
長さ1の列は既にソートされているから、何もすることはない。

サポートサイト Wikidot.com