マージソート

ホームアルゴリズム入門講座 > マージソート

マージソート

マージソートの基本データ

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

マージソートはアルゴリズム自体は単純ですが、ソースコードで表現すると再帰を使うため多少複雑になります。

マージソートはまず、要素を分割することから始まります。分割し終わったら、隣の要素同士で比較し、マージ(吸収・合併)します。分割とマージを繰り返すことによって、ソートを行います。

アルゴリズム初心者にとって理解するのが難しいかもしれませんが、アルゴリズムらしい美しさを持っていますので、ぜひ習得してください。

マージソートを行う関数 MargeSort(int[] basedata) があるとする。

MargeSort() は3つの部分から構成される。
1) basedata を2つに分ける部分(分けられない場合は戻る)
2) 2つに分けられた部分を再帰的に呼び出す部分
3) 2つに分けられた部分を並び替えながら合体させる部分

試しに
{5,4,3,2,1}
をマージソートしてみる。

*********************************
MargeSort({5,4,3,2,1})
1) {5,4} と {3,2,1} に分割された。
2) {5,4} を再帰的に呼び出す → [マージNo.1]へ → {4,5} ができた
2) {3,2,1} を再帰的に呼び出す → [マージNo.2]へ → {1,2,3} ができた
3) {4,5} と {1,2,3} をマージして {1,2,3,4,5} になった。
*********************************
(これより以下は「再帰的な呼び出し」による)

[マージNo.1]
MargeSort({5,4})
1) {5} と {4} に分割された
2) 再帰的に呼び出すが、もう分けられないので戻る
3) マージして {4,5} になった。呼び出し元へ戻る

[マージNo.2]
Marge({3,2,1})
1) {3} と {2,1} に分割された
2) {3} を再帰的に呼び出すが、もう分けられないので戻る
2) {2,1} を再帰的に呼び出す → [マージNo.3]へ → {1,2} ができた
3) {3} と {1,2} をマージして {1,2,3} になった。呼び出し元へ戻る

[マージNo.3]
Marge({2,1})
1) {2} と {1} に分割された
2) 再帰的に呼び出すが、もう分けられないので戻る

今度は9個の要素を図解的にマージソートしてみます。

 1) {6,3,8,5,4,7,9,2,1} (出発点!!)
 2) {6,3,8,5} {4,7,9,2,1}
 3) {6,3} {8,5}
 4) {6} {3}
 5) {3,6} (マージ!!)
 6) {8} {5}
 7) {5,8} (マージ!!)
 8) {3,5,6,8} (マージ!!)
 9) {4,7} {9,2,1}
10) {4} {7}
11) {4,7} (マージ!!)
12) {9} {2,1}
13) {2} {1}
14) {1,2} (マージ!!)
15) {1,2,9} (マージ!!)
16) {1,2,4,7,9} (マージ!!)
17) {1,2,3,4,5,6,7,8,9} (マージ!!)

マージソートの実装

using System;

namespace NewWorld
{
	class MainClass
	{
		private static int count = 0;
		
		public static void Main(string[] args)
		{
			int[] data = {6,3,8,5,4,7,9,2,1};
			MargeSort(data);
			foreach(int i in data)
				Console.WriteLine(i);
			
			Console.WriteLine("{0} times",count);
		}
		
		public static void MargeSort(int[] basedata)
		{
			if(basedata.Length == 2)
			{
				if(basedata[0] > basedata[1])
				{
					int m = basedata[0];
					basedata[0] = basedata[1];
					basedata[1] = m;
					
					count++;
				}
			}
			else if(basedata.Length > 1)
			{
				int[] data1 = new int[basedata.Length / 2];
				int[] data2 = new int[basedata.Length - data1.Length];
				for(int i=0;i<data1.Length;i++)
					data1[i] = basedata[i];
				for(int i=0;i<data2.Length;i++)
					data2[i] = basedata[data1.Length + i];
				
				MargeSort(data1);
				MargeSort(data2);
				
				int a = 0;
				int b = 0;
				for(int n=0;n < basedata.Length;n++)
				{
					if(a >= data1.Length)
					{
						basedata[n] = data2[b];
						b++;
					}
					else if (b >= data2.Length )
					{
						basedata[n] = data1[a];
						a++;
					}
					else
					{
						if(data2[b] < data1[a])
						{
							basedata[n] = data2[b];
							b++;
						}
						else
						{
							basedata[n] = data1[a];
							a++;
						}
					}
					count++;
				}
			}
		}
	}
}

実装はアルゴリズムの通りやれば問題ありませんが、再帰に慣れていないと非常に難しいと思います。

このプログラムはマージソートの定義と分割統治法の概念から私が独自に作ったものですが、かなり時間がかかってしまいました。配列の要素数をオーバーしてしまう例外が発生し、それに対処するのに手間取りました。

このプログラムでは要素数が2のときは分割せずにいきなり比較します。この部分がなくてもソートは可能ですが、おおよそ n / 2 回だけ早くなります。計算量自体は変わりません。

また、マージする際のifのネストは、1個でも論理演算子を使えば記述できます。ここではわかりやすいようにネストしています。なお、count は回数を数える変数であり、アルゴリズムとは関係ありません。

分割統治法とO(n log n)

マージソートは「分割統治法」という問題解決策の具体的な事例です。分割統治法を用いたソートは主に「マージソート」と「クイックソート」があり、いずれも高速に動作します。

分割統治法とは、「大きな問題」を「小さな問題」に分割するという手法です。マージソートは、「大きな問題」である要素全体を「小さな問題」である2個の要素を持つ配列にまで分割してからソートします。

また、計算量 n log n というのも、分割統治法の恩恵です。アルゴリズムで log を使うときは、底は10ではなく、2です。マージソートのように、「2等分」することが多く、また、コンピュータ自体もビットで構成されるため、10よりも2の方が便利だからです。

マージソートにおける計算量 n log n の n log の部分はもちろん分割です。そして、nがマージです。一般に、正確なソートアルゴリズムは最低でも n log n の計算量を必要とすることが知られています。

バブルソートや挿入ソートの計算量は n2 ですから、例えば要素が16あったとすると最悪の場合 256 の計算が必要になります。一方、マージソートは 32 でソートが完了します。このように、分割統治法による n log n は画期的なのです。

とはいえ、マージソートには欠点があります。それは、データ以外の記憶領域を必要とする点です。上のプログラムでは data1 と data2 を用意しており、n の記憶領域が別個に必要になります。

アルゴリズムをきちんと理解して、これらの特徴を持ったソートを使い分けたいものです。