ALDS1_5_B Merge Sortを解く話

AOJのマージソートを実装する問題です．

特徴

・分割統治と再帰を上手く使ったソーティングアルゴリズム

・配列を1要素になるまで分割してくっつき直すときに比較．

アルゴリズム

Mergesort(array, left, right)

1. 要素数が1ならソート済みなのでreturn．（実装では left + 1 < right)
2. 配列を半分にする．
3. 左半分をMergesortに渡す（実装では再帰を使う）．
4. 右半分をMergesortに渡す（同じく再帰）．
5. マージ．

計算量

マージがn回，分割が回なので計算量は．

実装

分割した配列の末尾に番兵を配置するのに注意．

gist46eccdb4e29c4cc01cc448b894cf8814

感想

マージソートに対する僕のイメージは全結合していないニューラルネット．

1. 入力層にこれからソートする配列を渡す．
2. 層を進むにつれて配列は分割され次の層へ．
3. 一番真ん中の層が配列が1要素数になるまで分割された状態．
4. この後の層では比較とマージをする．

てな感じ．これで覚えておけばそらで書けるかな．