マージソートの可視化

はじめに

ちょうと1年前くらいに
www.mtioutput.com
といった記事を書きました。タイトルの通り、選択ソートとバブルソートを可視化しました。

一定の反響があったので、今回はマージソートの可視化を行います。
使用するのも前回同様 R言語です。

マージソートの可視化

準備

マージソートとは、

1. 配列を適当な長さでぶつ切りにする
2. それぞれをソートする。再帰でもいいし別のアルゴリズムでもいい
3. できた配列を混ぜる

問題を大きいまま解かないということがキモで、典型的な分割統治形のアルゴリズムといえる。
（ニコニコ大百科 より抜粋）

今回は配列をx、マージソート関数をf、基準値をpivotとし、基準値は配列xの平均値とします。

pivot=ave(x)[[1]]

実装

配列xの各値が基準(pivot)より大きいか小さいかで配列をleft,rightに分割

for(k in 1:length(x))
    {
      if(x[k] <= pivot)
      {    
        left <- append(left,x[k])
        count <- count + 1
      }
      else
      {
        right <- append(right,x[k])
      }
    }

分割したleft、rightを再起的にまたfにつっこむ流れにしました。
countは配列の結合で用いる配列の引数としてfに渡しています。

分割の回数で上記のマージソートを可視化したものが以下になります。

一秒毎に8回目までのソートの経過を可視化しました。選択ソートやバブルソートとは全く異なっていることが分かります。

おまけ

おまけとして、pivotを

pivot_t=ave(x[1:2])[[1]]

とすればどうなるでしょう。直観的には、基準が前の二つの平均値となるので少し偏ったpivotで配列を分割していくことになりそうです。
同じく8回目までのソートの経過を可視化したものが以下になります。

8回だけでは並べ替えきれていない感じがします。

以上、マージソートの可視化でした。*1

*1:分割と併合を繰り返したものの経過の可視化はマージソートのWikipediaにも掲載されていましたのでご参考まで