マージソート実装・詳しい計算量解説

マージソート(Merge Sort)

このサイトでのマージソートの定義は以下の通りです。¹

計算量 $O(N \log N)$

マージソートのアルゴリズム

マージソートは「分割統治法」を用いた効率的なソートアルゴリズムです。

リストを再帰的に半分に分割し、各部分をソートしてから統合（マージ）することで、

全体をソートします。このアルゴリズムは安定ソートに分類され、大規模なデータセットに適しています。

詳しく手順を説明すると以下の通りです。

1. 配列を 2 つの部分に分割します。
2. 各部分を再帰的にマージソートを適用します。
3. ソートされた 2 つの部分の先頭同士を比較し、 1 つに統合（マージ）します。

これにより、部分配列が順次統合され、最終的に完全にソートされた配列が得られます。

以下に C 言語での実装例を示します。

void merge(int *d, int left, int right){
	int n=right-left+1;//データ数
	int m=(left+right)/2;//middle
	int *nd = (int *)calloc(right-left+1, sizeof(int));//ソート済み集合
	int lidx=left;//左集合の最小値idx
	int ridx=m+1;//右集合の最小値idx
	int count=0;//ndに格納するためのidx
	while (lidx<m+1&&ridx<right+1){
		if(d[lidx]<d[ridx]){
			nd[count]=d[lidx];
			lidx++;
		}
		else{
			nd[count]=d[ridx];
			ridx++;
		}
		count++;
	}
	while(lidx<m+1){
		nd[count]=d[lidx];
		lidx++;
		count++;
	}
	while(ridx<right+1){
		nd[count]=d[ridx];
		ridx++;
		count++;
	}
	for(int i=0;i<n;i++){
		d[left+i]=nd[i];
	}
	free(nd);
	return;
}
 
void mergeSort(int *d, int left, int right)
{
	int i,j;
	if (left==right){
		return;
	}
	int m=(left+right)/2;
	mergeSort(d,left,m);
	mergeSort(d,m+1,right);
	merge(d,left,right);
	return;
}

計算量の議論

データ数 $N$ は $N=2^k$ と表せるとし、マージソートの計算量を議論します。

マージソートでソートするためにかかる比較回数を$Q(2^k)$とします。

データ数 $2^k$ のデータをソートするとき、データを 2 つに分割し、それぞれをソートし、ソートされた 2 つの先頭を比較しすべての部分をソートするので、最良の場合以下のような式が成り立ちます。

$Q(2^k) = 2Q(2^{k-1}) + 2^{k-1}$

この式を展開していくと以下のようになります。

このように展開を最後まで行うと以下のような式が成り立ちます。

ここで、$Q(2^1)$ は 2 つの要素をソートするのにかかる比較回数であり、2 つの要素をソートするのにかかる比較回数は 1 回です。

よって $Q(2^k) = k \times 2^{k-1}$ となります。

データ数 $N$ は $N=2^k$ と表せるので、$k=\log_2 N$ となります。

よって、$Q()$ を $N$ の関数として表すと以下のようになります。

よって、マージソートの計算量は $O(N \log N)$ となります。

マージソートの計算量は、分割する工程が $O(\log N)$ で行われ、各分割でのマージが $O(N)$ の計算量で実行されるため、全体の計算量は $O(N \log N)$ となります。

この計算量はソートアルゴリズムの中でも非常に優秀で、特に大規模なデータセットでその効果が顕著に現れます。

マージソートは、メモリ効率の観点ではデータ量に応じた追加のメモリが必要になるため、場合によってはクイックソートやヒープソートといった他のアルゴリズムの方が適していることもあります。

しかし、安定性と計算量のバランスから、マージソートはしばしばデフォルトのソートアルゴリズムとして選択されます。