先頭へ戻る

マージソート | Programming Place Plus 用語集

Programming Place Plus トップページ用語集

先頭へ戻る

名称

解説

ソートアルゴリズムの一種で、ソートされている2つのデータ列をマージ(併合)する作業を繰り返すことによって、ソートを行う手法です。

2つのデータ列がソート済みであれば、それぞれの先頭の要素のうち、小さいもの(あるいは大きいもの)を選べば、そのデータは必ず、全体の中での最小値(あるいは最大値)です。このように選び出したデータを、新しいデータ列へ移動させることを繰り返せば、すべてのデータが新しいデータ列に移動し終えたとき、そのデータ列はソート済みになっています。2つのデータ列を合体させて、新しいデータ列を生み出すことをマージ(併合)と呼び、マージを繰り返し利用することからマージソートと呼ばれます。

ソートすることが目的でありながら、ソート済みのデータ列を用意しなければならないことが矛盾しているようですが、ソート済みのデータ列は、ソートしたいデータ列を分解して作り出します。そのためにまず、ソートしたいデータ列を、データが1つしか含まれないデータ列になるまで2分割していく作業を再帰的に繰り返すことから始めます。完全にばらばらに分解されたら、隣のデータ列とのマージを行い、それを再帰的に繰り返すことでマージソートが完成します。

計算量としては O(n log n) で、対象のデータの並び方に影響されない特徴があります。また、安定ソートとして実装できます(マージの実装を間違えると、安定ソートにならない)。

2つのデータ列を1つのデータにマージする作業をおこなうため、ソート対象が配列の場合、同サイズの追加のメモリ領域が必要となることが欠点とされます。

マージソートの解説がアルゴリズムとデータ構造編【整列】第7章にあります。


参考リンク

更新履歴


用語集のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー