「マージソート」の編集履歴（バックアップ）一覧はこちら

マージソート - (2010/01/25 (月) 19:19:41) の１つ前との変更点

追加された行は緑色になります。

削除された行は赤色になります。

整列アルゴリズムのひとつ。
実行時間はO(nlogn)程度であり、安定な整列法である。また、クイックソートと異なり、どのようなデータに対しても高速であるが、データと同程度の作業用記憶領域を必要とする。 

下記プログラムでは、マージソートが安定であることを示すために整列データに整列に使用するキー欄（key）以外に情報欄（info）を持たせている。さらに高速にするには、11行目を if If first - last < 10 Then とし、44行目で Else simplesort などと挿入ソートなどに切り替えればよい。 
 プログラミング掲示板「ソートロジック大会」なども参照のこと
***マージ

整列したデータをまとめてひとつの整列したデータにすることをマージ（併合）という。整列した大きなデータを更新する際は、追加分のデータを整列した後に整列済みのデータにマージするほうが圧倒的に速い。
#asciiart(blockquote){
Type SORT
	key As Integer
	info As Integer
End Type
Const N = 10
Dim a[N] As SORT			'整列させる配列
Dim work[N / 2 + 1] As SORT		'作業用の配列
Sub mergesort(first As Integer, last As Integer)
	Dim middle As Integer
	Dim i As Integer, j As Integer, k As Integer, p As Integer
	If first < last Then
		middle = (first + last) / 2
		'再起呼び出し
		mergesort(first, middle)
		mergesort(middle + 1, last)
		'
		p = 0
		For i = first To middle
			work[p] = a[i]		'同じ構造体であれば等号でOK
			p = p + 1
		Next i
		i = middle + 1
		j = 0
		k = first
		While i <= last And j < p
			If work[j].key <= a[i].key Then
				a[k].key = work[j].key
				a[k].info = work[j].info
				k = k + 1
				j = j + 1
			Else
				a[k].key = a[i].key
				a[k].info = a[i].info
				k = k + 1
				i = i + 1
			End If
		Wend
		While j < p
			a[k].key = work[j].key
			a[k].info = work[j].info
			k = k + 1
			j = j + 1
		Wend
	End If
End Sub
}