マージソート 【merge sorting】 併合ソート / 併合整列法

概要

マージソート（merge sorting）とは、与えられたデータ列を大小などの順序通りになるよう並べ替えるソート(整列)アルゴリズムの一つで、データ列を細かく分割し、整列しながら次第に併合していくもの。

最初にデータ列を半分、そのまた半分と分割していき、一つ一つのデータがバラバラになるまで分割する。その後、最初は単体のデータ同士を、続いて要素数が同じ列同士を順に併合（マージ）していく。

併合する際は二つの列の先頭のデータを比較し、小さい（あるいは大きい）方を取り除いて併合列に追加する。二つの列の内部はすでに整列済みであるため、両方の列のデータが無くなるまでこの手順を繰り返すことで、整列済みの併合列を得ることができる。列が一つの併合されたら整列完了となる。

平均計算時間も最悪計算時間もO（nlogn）となる極めて高速なソートアルゴリズムだが、元のデータ列の他に作業用の記憶領域を必要とする。実装上の配慮により、同じ大きさの要素の順序が入れ替わらない安定ソートとすることができる。

この記事の著者 ： (株)インセプト IT用語辞典 e-Words 編集部
1997年8月より「IT用語辞典 e-Words」を執筆・編集しています。累計公開記事数は1万ページ以上、累計サイト訪問者数は1億人以上です。学術論文や官公庁の資料などへも多数の記事が引用・参照されています。