※「セキュリティ保護のため...」というメッセージが出る方・日本語が入力できない方へ
(5)マージソート

  これは面白い考え方のソートである。ソート前の元データを観察すると、
  その中には、偶然、順序よく並んでいる箇所がいくつかある。

  マージソートでは、データの並びを「ソート済みのデータが幾つか集まっ
  たもの」と考える。そしてそれを全部マージして、ひとつのソート済みの
  データに変身させるのである。これもクイックソート並みに高速なソート。

  クイックソートが嫌いな人たちがよく使用していた。

【Coding Sample】(Merge Sort)

void CSortDlg::MergeSort()
{
	//Split Array to Sorted-subarrays
	int i,j,k,s1,s2,e1,e2;
	long* tmp = new long[m_dcnt];
loop_1:
	s1=0;
loop_2:
	e1=GetLastNo(s1);
	s2=e1+1;
	if (s2>=m_dcnt)
	{
		if (s1==0)
			goto loop_e;
		else
			goto loop_1;
	}
	e2=GetLastNo(s2);

	//Merge s1〜e1 and s2〜e2  (e1+1=s2)
	i=s1;
	j=s2;
	k=0;
loop_3:
	if (i<=e1 && j<=e2)
	{
		if (m_data[i]<m_data[j])
			tmp[k++] = m_data[i++];
		else
			tmp[k++] = m_data[j++];
	}
	else
	{
		if (i<=e1)
			tmp[k++] = m_data[i++];
		else
			tmp[k++] = m_data[j++];
	}
	if (i<=e1 || j<=e2)
		goto loop_3;

	for (k=0; k<e2-s1+1; k++)
		m_data[s1+k] = tmp[k];

	s1 = e2 + 1;
	if (s1<m_dcnt)
		goto loop_2;
	else
		goto loop_1;

loop_e:
	delete [] tmp;

}
long CSortDlg::GetLastNo(long st)
{
	while(st<m_dcnt-1 && m_data[st]<=m_data[st+1])
		st++;

	return st;
}


【実行時間】(Pentium-75MHz VisualC++5.0 Release Mode)

　　             件数　   乱順　　　　正順　　　　逆順
MergeSort(r)     1000    0.00000     0.00000     0.00000
MergeSort(r)    10000    0.05000     0.00000     0.05000
MergeSort(r)    30000    0.17000     0.00000     0.17000
MergeSort(r)   100000    0.88000     0.00000     0.71000
MergeSort(r)   300000    2.97000     0.06000     2.14000
MergeSort(r)  1000000   10.38000     0.11000     7.20000
MergeSort(r)  3000000   44.00000     0.33000    24.11000

　マージソートもちょっと考えると逆順に弱そうだが、逆順に並んでいると
　いうことは、部分列が半分・半分で出来ていくので、結果的には乱順より
　速くなってしまうのです。これがマージソートの面白いところです。
　
　マージソートは上記のCのような普通の言語で書くとまぁまぁ入り組んで
　いますが、実はリスト処理機能を持っている言語で書くと、あまりにも
　シンプルになります。