マージソート - abwiki @ ウィキ (ActiveBasic非公式wiki)

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

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

プログラミング掲示板「ソートロジック大会」なども参照のこと

マージ

整列したデータをまとめてひとつの整列したデータにすることをマージ（併合）という。整列した大きなデータを更新する際は、追加分のデータを整列した後に整列済みのデータにマージするほうが圧倒的に速い。

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