A little bit of everything

元・情報系大学院生の備忘録

マージソート

アルゴリズム

  1. 配列の長さが1以下なら、ソート済みなので終了。長さ2以上なら2へ。
  2. 配列を等分し、この2つの配列にそれぞれマージソートを適用した後、3へ。
  3. 2つの配列をマージアルゴリズムでマージする。


手順2で再帰的にマージソートを使っているので、日本語にするとちょっと違和感があるかもしれないけど、これが本来のアルゴリズムです!

分割フェーズ f:id:yuukiyg:20160117014416p:plain

マージフェーズ f:id:yuukiyg:20160117014508p:plain