4件
平均O(n log n)はクイックソートと並ぶが、ランダムな配列で実測するとクイックソートよりやや遅い。ただし、運が悪くてもO(n log n)で済んだり、最速O(n)を出せる変形があったりといった渋い特徴を持つ通好みのソートである。普通は安定ソート。
ちなみに考案したのはかの火星人ジョン・フォン・ノイマン。1945年生まれという計算機科学史上でも最長老クラスのアルゴリズムである。歴史が長いだけに変種も多い。
原理
すでにソート済みの二つの配列があって、それらを一つにまとめたいとする。一番小さい値はどちらかの先頭にあるからそれを取り、以下両方の配列がなくなるまで繰り返せばソート済みの一本の配列が作れる。
これをひっくり返して考えるのがマージソートである。
問題を大きいまま解かないということがキモで、典型的な分割統治形のアルゴリズムといえる。クイックソートと違って基準値による上からの仕分けが不要であり、適当にぶつ切りで動かせるため、並列化などを自然にできる点もポイントである。
性能検討
数値的には、クイックソートに匹敵する速さで、かつ安定した性能を出すという点につきる。出目の悪さで時々遅くなるという弱点がないので信頼性は抜群。
また連結リストとの相性もよい。連結リストはランダムアクセスに弱いため、後ろの方に頻繁に参照が発生するソートだとうまく動かないのだが、マージソートは混ぜる時に先頭要素しか見ないので、最初のぶつ切りさえ済ませてしまえば後は自然に繋いでいくだけで済む。
さらにオンメモリに載りきらない馬鹿デカいデータのソートにも使える。ランダムアクセス不要で、終わった所を順番に格納できるという性質は色々と応用範囲が広く、実際元々はディスク上のデータのソート用途に長らく使われていた。
弱点は外部ソートの宿命として混ぜた配列用の置き場が必要なこと。インプレイスな実装もないわけではないのだが、本来的に内部ソートなアルゴリズムほど省スペースというわけにはいかず、メモリ面でそれなりに配慮がいる。ちなみに連結リストの場合、これまたリストの継ぎ替えだけで新配列を作れるためバッファ不要となる。連結リストとマージソートの相性は鉄板である。
なおマージソートは仕掛けが大掛かりなだけにオーバヘッドも大きく、小さい配列のソートには今ひとつ不向きである。そのため最下層のソート列は挿入ソートや選択ソートといったトリビアルなアルゴリズムで用意し、ある程度大きな塊を作ったところで混ぜていくという実装が多い。
関連項目
- 3
- 0pt
