マージソート単語

マージソート

マージソートはソートアルゴリズムの一種。

均O(n log n)はクイックソートと並ぶが、ランダム配列で実測するとクイックソートよりやや遅い。ただし、運が悪くてもO(n log n)で済んだり、最速O(n)を出せる変形があったりといった渋い特徴を持つ通好みのソートである。普通は安定ソート

ちなみに考案したのはかの火星人ジョン・フォン・ノイマン1945年生まれという計算機科学史上でも最長老クラスアルゴリズムである。歴史が長いだけに変種も多い。

原理

すでにソート済みの二つの配列があって、それらを一つにまとめたいとする。一番小さい値はどちらかの先頭にあるからそれを取り、以下両方の配列がなくなるまで繰り返せばソート済みの一本の配列が作れる。

これをひっくり返して考えるのがマージソートである。

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

問題を大きいまま解かないということがキモで、典的な分割統治形のアルゴリズムといえる。クイックソートと違って基準値による上からの仕分けが不要であり、適当にぶつ切りで動かせるため、並列化などを自然にできる点もポイントである。

性能検討

数値的には、クイックソートに匹敵する速さで、かつ安定した性を出すという点につきる。出の悪さで時々遅くなるという弱点がないので信頼性は抜群。

また連結リストとの相性もよい。連結リストランダムアクセスに弱いため、後ろの方に頻繁に参照が発生するソートだとうまく動かないのだが、マージソートは混ぜる時に先頭要素しか見ないので、最初のぶつ切りさえ済ませてしまえば後は自然に繋いでいくだけで済む。

さらにオンメモリに載りきらない馬鹿デカいデータソートにも使える。ランダムアクセス不要で、終わった所を順番に格納できるという性質は色々と応用範囲が広く、実際元々はディスク上のデータソート用途に長らく使われていた。

弱点は外部ソートの宿命として混ぜた配列用の置き場が必要なこと。インプレイスな実装もないわけではないのだが、本来的に内部ソートアルゴリズムほどスペースというわけにはいかず、メモリ面でそれなりに配慮がいる。ちなみに連結リストの場合、これまたリストの継ぎ替えだけで新配列を作れるためバッファ不要となる。連結リストとマージソートの相性は鉄板である。

なおマージソートは仕掛けが大掛かりなだけにオーバヘッドも大きく、小さい配列ソートには今ひとつ不向きである。そのため最下層のソート列は挿入ソート選択ソートといったトリビアルなアルゴリズムで用意し、ある程度大きな塊を作ったところで混ぜていくという実装が多い。

関連項目

【スポンサーリンク】

スマホ版URL:
https://dic.nicovideo.jp/t/a/%E3%83%9E%E3%83%BC%E3%82%B8%E3%82%BD%E3%83%BC%E3%83%88

この記事の掲示板に最近描かれたお絵カキコ

お絵カキコがありません

この記事の掲示板に最近投稿されたピコカキコ

ピコカキコがありません

マージソート

1 ななしのよっしん
2017/01/09(月) 07:22:50 ID: UM+MYovGAy
好きな方のキャラを選んでいけば順位が出る「○○○キャラソート」というのは、大抵はマージソートを使っている。
最悪計算量がO(𝑛 log 𝑛)であるのが理由の一つか。

急上昇ワード