【VBA】マージソートアルゴリズムの実装｜配列を高速に並べ替える方法

2025年8月17日

はじめに

VBAで配列の要素を並べ替える（ソートする）際、バブルソートのような単純なアルゴリズムは理解しやすいですが、要素数が多くなると処理に非常に時間がかかってしまいます。

より大規模なデータを高速にソートするためのアルゴリズムの一つが「マージソート」です。マージソートは、「分割統治法」という考え方に基づいた、非常に効率的で安定したソートアルゴリズムです。

この記事では、マージソートの考え方と、それをVBAでどのように実装するかを、コードの解説付きで詳しくご紹介します。

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

マージソートは、以下の3つのステップで動作します。

分割 (Divide): 並べ替えたいリストを、要素が1つになるまで、どんどん半分に分割していきます。
統治 (Conquer): 要素が1つだけのリストは、それ自体が既に「ソート済み」と見なせます。
結合 (Merge): 分割したリストを、今度は逆に、大小を比較しながら正しい順序で一つのリストに**統合（マージ）**していきます。これを繰り返すことで、最終的に全体がソートされたリストが完成します。

VBAでの実装コード

以下のコードは、ランダムな数値が入った配列を生成し、それをマージソートで昇順に並べ替えて、結果をシートに書き出すものです。

完成コード

' マージソートの実行サンプル
Sub RunMergeSortExample()
    Dim dataArray() As Variant
    Dim arraySize As Long, i As Long
    
    arraySize = 20 ' 生成するデータの数
    ReDim dataArray(1 To arraySize)
    
    '--- 1. ランダムなテストデータを生成し、A列に書き出し ---
    For i = 1 To arraySize
        Randomize
        dataArray(i) = Int(1000 * Rnd + 1)
        Worksheets("Sheet1").Range("A1").Cells(i, 1).Value = dataArray(i)
    Next i
    
    '--- 2. マージソート関数を実行 ---
    dataArray = ExecuteMergeSort(dataArray)
    
    '--- 3. ソート後の結果をB列に書き出し ---
    With Worksheets("Sheet1").Range("B1")
        For i = 1 To arraySize
            .Cells(i, 1).Value = dataArray(i)
        Next i
    End With
    
    MsgBox "A列の値を昇順ソートしてB列に書き込みました。"
End Sub


' マージソートを再帰的に実行する関数
Private Function ExecuteMergeSort(ByVal targetArray As Variant) As Variant
    Dim arrayCount As Long
    arrayCount = UBound(targetArray)
    
    '--- 分割のベースケース：要素数が1以下の場合は、そのまま返す ---
    If arrayCount <= 1 Then
        ExecuteMergeSort = targetArray
        Exit Function
    End If
    
    '--- 1. 分割 (Divide) ---
    Dim splitIndex As Long
    Dim leftHalf() As Variant, rightHalf() As Variant
    Dim i As Long
    
    splitIndex = arrayCount \ 2 ' 配列を半分にするためのインデックス
    
    ' 左半分を準備
    ReDim leftHalf(1 To splitIndex)
    For i = 1 To splitIndex
        leftHalf(i) = targetArray(i)
    Next i
    
    ' 右半分を準備
    ReDim rightHalf(1 To arrayCount - splitIndex)
    For i = 1 To arrayCount - splitIndex
        rightHalf(i) = targetArray(splitIndex + i)
    Next i
    
    '--- 2. 統治 (Conquer) - 再帰呼び出し ---
    leftHalf = ExecuteMergeSort(leftHalf)
    rightHalf = ExecuteMergeSort(rightHalf)
    
    '--- 3. 結合 (Merge) ---
    Dim leftIdx As Long, rightIdx As Long, k As Long
    leftIdx = 1
    rightIdx = 1
    
    For k = 1 To arrayCount
        If leftIdx > UBound(leftHalf) Then
            ' 左が空になったら、右の残りを全て入れる
            targetArray(k) = rightHalf(rightIdx)
            rightIdx = rightIdx + 1
        ElseIf rightIdx > UBound(rightHalf) Then
            ' 右が空になったら、左の残りを全て入れる
            targetArray(k) = leftHalf(leftIdx)
            leftIdx = leftIdx + 1
        Else
            ' 左右を比較し、小さい方を結果に入れる
            If leftHalf(leftIdx) <= rightHalf(rightIdx) Then
                targetArray(k) = leftHalf(leftIdx)
                leftIdx = leftIdx + 1
            Else
                targetArray(k) = rightHalf(rightIdx)
                rightIdx = rightIdx + 1
            End If
        End If
    Next k
    
    ExecuteMergeSort = targetArray
End Function

コードの解説

`ExecuteMergeSort` 関数

この関数は、自分自身を呼び出す「再帰」というテクニックを使っています。

ベースケース: If arrayCount <= 1 Then の部分が、再帰の停止条件です。渡された配列の要素が1つ以下になったら、それ以上分割せず、配列をそのまま返します。
分割処理: 配列を splitIndex を基準に、leftHalf と rightHalf という2つの新しい配列にコピーしています。
再帰呼び出し: 作成した leftHalf と rightHalf を、それぞれ再び ExecuteMergeSort 関数に渡して、さらに分割・ソートさせます。
結合処理: 2つのソート済みの小さな配列 (leftHalf, rightHalf) を、先頭から比較しながら、元の targetArray に正しい順序で戻していきます。これがマージ（統合）のプロセスです。