マージソートとは
マージソート のマージ(merge)とは、2つのソート済データを併合(マージ)することで1つのソート済データを取得する処理をさします。マージソートでは再帰的な呼び出しにより、十分に小さく分割してからそれを統合(マージ)します。分割統治法と呼ばれる手法です。
マージを行う際には、2つのデータの内の片方を外部領域に保持し、小さい(大きい)データからもとの領域に戻すことで、ソート済のデータ作成します。
マージソートは 安定 な 外部 ソートです。平均計算量・最悪計算量ともに O(n log n) のため安定して高速で動作します。ただし、前述の通り2つのデータをマージする際に、外部領域を必要とします。最後のマージ n/2 個のデータを保持できる領域が必要になります。つまりメモリ使用量に O(n) を必要とします。
マージソートのシミュレーション
背景色が黄色のタイミングで比較が実行されています。緑色のデータが現在分割統治中のデータです。
以下の図を参考に、シミュレーションの動きを見ると具体的な処理がイメージできます。
アルゴリズムの解説
- データを2つのデータに分割します。
- 分割したデータをさらにマージソートでソートします。
- 分割されたデータをマージ(小さいほうから順に取り出して並べる)
マージの考え方
分割された左右のデータ領域をマージするには、まず左側のデータを外部領域に退避します。あとは、退避したデータと右側のデータについて、先頭の要素から順に値を比較し、元の領域に戻す作業を繰り返せばよいです。
この時、退避した値を並べ終わればマージは終了です。なぜなら右のデータをもとの位置にありそれが正しい位置だからです。
右側のデータが並べ終わったら、退避していた右側のデータをすべて元の領域に戻して完了です。
いずれの場合も、おかしな形でデータが上書きされないことを確認しておきましょう。
サンプルコード
C#
public static void MergeSort<T>(T[] array) where T : IComparable<T>
{
var work = new T[(array.Length + 1) / 2];
MergeSort(array, 0, array.Length - 1, work);
}
public static void MergeSort<T>(T[] array, int left, int right, T[] work) where T : IComparable<T>
{
var mid = left + (right - left) / 2;
if (left == right) return;
MergeSort(array, left, mid, work); // 分割した左側をマージソート
MergeSort(array, mid + 1, right, work); // 分割した右側をマージソート
Merge(array, left, right, mid, work); // ソートされた左右のデータをマージ
}
public static void Merge<T>(T[] ary, int left, int right, int mid, T[] work) where T : IComparable<T>
{
// 左部分を作業領域に退避
for (int i = left; i <= mid; i++)
{
work[i - left] = ary[i];
}
int l = left;
int r = mid + 1;
// 左部分と右部分(作業領域)をマージ
while (true)
{
// 値を入れるインデックスk
int k = l + r - (mid + 1);
// 左部分(作業領域)が並べ終わったらマージ完了(右部分残りはもとの位置のまま)
if (l > mid) break;
// 右部分が並べ終わったら左部分(作業領域)をすべて並べて完了
if (r > right)
{
while (l <= mid)
{
k = l + r - (mid + 1);
ary[k] = work[l++ - left];
}
break;
}
// 小さい方の値を配列に並べ、インクリメントしておく
ary[k] = work[l - left].CompareTo(ary[r]) < 0 ? work[l++ - left] : ary[r++];
}
}
public static void Swap<T>(ref T a, ref T b)
{
var tmp = a;
a = b;
b = tmp;
}