自分の恥をさらすと、ごくごく最近まで「マージ」を単に配列を前後に結合することだと思っていました……。
[1,2] + [3,4,5] => [1,2,3,4,5]
このせいで「マージソート」なるものがさっぱり理解できず、ずいぶんと長い間学習を放棄していました……。個人的に再帰がものすごく苦手(というか、どこでどう使うのかがいまだによくわかっていない)ということもあり、逃げ回っていたということもあります。
が、最近偶然読んでいた本でマージの本当の意味を会得。ばかばかしいですが、個人的にはかなりの大発見なので、記事として公開しておきます。
もちろん「マージ」とはふたつの配列を単につなぎ合わせることではありません。「ふたつの配列の先頭を見比べ、小さいものを取り出して、別に用意した配列に追加していく」これこそが真の「マージ」です。したがって、ひとつの配列を極限までばらばらにしたのちにマージしていけば、最終的にはソートされた配列があらわれるはず――これでやっと「マージソート」が理解できます!
なおこの手の説明はWikipedia「マージ」とWikipedia「マージソート」がもっともわかりやすかったと思います。
とりあえず理解できたところで、実際に実装していきます。まずRuby。
書きやすく読みやすいコードが書けました(そのはず)。
次に最近お勉強中のC言語――といきたいところですが、途中で挫折。やはりCは配列周りがややこしい! 結局逃げてC++を使いました。std::vectorは本当に便利ですね。
メモリ? 解放? 知らない子ですね。ガベージコレクション万歳!
