マージソートの処理の流れを追ってみた

PHPでマージソートを書き、その処理を追ってみた。

コード

出力結果

流れ

mergesortは与えられた配列を$leftと$rightに分割する、その処理は内部で再帰的に呼び出され 配列の要素は一旦最小単位(1つ)になる。

その後、隣り合うそれぞれの単位を交互に比較し、並び替えながら、順番通りにマージしていく。

最小単位に分割される前、

(5,1,2,3,6,4)

最小単位に分割された後、

(5),(1),(2),(6),(3),(4)

マージ開始

マージを繰り返すごとにまとまりになっていくことがわかる。

1. (5),(1,2),(6),(3),(4)

2. (1,2,5)(6),(3),(4)

3. (1,2,5)(6),(3,4)

4. (1,2,5)(3,4,6)

マージ終了

1. (1,2,3,4,5,6)

おまけ

記事書くときとか、簡単なコードを共有する際にvimからGistに直接投稿できるgist.vimが便利だ。 - vimでソーシャルなスニペットメモをはじめる～gist.vim