RSS
ソートのアルゴリズムの一種で、ソートされている２つのデータ列をマージ（併合）する作業を繰り返すことによって、ソートを行う手法です。
２つのデータ列がソート済みであれば、それぞれの先頭の要素のうち、小さいもの（あるいは大きいもの）を選べば、そのデータは必ず、全体の中での最小値（あるいは最大値）です。このように選び出したデータを、新しいデータ列へ移動させることを繰り返せば、すべてのデータが新しいデータ列に移動し終えたとき、そのデータ列はソート済みになっています。２つのデータ列を合体させて、新しいデータ列を生み出すことをマージ（併合）と呼び、マージを繰り返し利用することからマージソートと呼ばれます。
ソートすることが目的でありながら、ソート済みのデータ列を用意しなければならないことが矛盾しているようですが、ソート済みのデータ列は、ソートしたいデータ列を分解して作り出します。そのためにまず、ソートしたいデータ列を、データが１つしか含まれないデータ列になるまで２分割していく作業を再帰的に繰り返すことから始めます。完全にばらばらに分解されたら、隣のデータ列とのマージを行い、それを再帰的に繰り返すことでマージソートが完成します。
計算量としては O(n log n) で、対象のデータの並び方に影響されない特徴があります。また、安定ソートとして実装できます（マージの実装を間違えると、安定ソートにならない）。
２つのデータ列を１つのデータにマージする作業をおこなうため、ソート対象が配列の場合、同サイズの追加のメモリ領域が必要となることが欠点とされます。
マージソートの解説がアルゴリズムとデータ構造編【整列】第７章にあります。
Programming Place Plus のトップページへ
| はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
| X で ポスト／フォロー | LINE で送る | noteで書く |
|
RSS
|
管理者情報 | プライバシーポリシー |