memo-09.ソートとマージ（５）マージソート

ソートとマージについて（5）マージソート
- 5．マージソート

ソートとマージについて（5）マージソート

5．マージソート

マージソートは、ソートすべきデータを再帰的に2分割する作業を繰り返し、それぞれの集合の要素が1つになったら、大小を比較しながらマージ（統合）していくソート方法です。
マージについては　前回ソートとマージについて（４）マージでご紹介していますのでそちらも参考にしてください。

5.1　分割後ソートされていく様子

5.2　フローチャート

MergeSortのプログラムフローを書くのは難しいです。
何故なら、配列の要素を２分割する作業を繰り返して集合の要素が１件になったら、保留状態になっている統合作業を逆から順番に実行していく再帰的アルゴリズムだからです。
　　　
下記の図は概略フローです。実際のサンプルデータがソートされていく図と併せて御覧下さい。

□A、□B、□C　は上記の概略フローの※A、※B、※Cに対応しています。
wka は Mergeサブから戻ってきたときの、Arr の内容（Left ～Right）です。
配列の位置番号はゼロ起算です。

5.3　MergeSortのコード（VBA)

MergeSortのコードです。
配列の位置番はゼロ起算です。

'＜Merge&Sort TestPG＞
 Public Sub TestMergeSort()  
    Dim d As Variant 
    data = Array(44, 13, 21, 51, 8, 14, 66, 9)  　  　　’サンプルデータ
    Call MergeSort(data, LBound(data), UBound(data))    'MergeSort(Data,0,7)       
  End Sub　
'***********************************************************************************
　'　＜MergeSort（Arr,Left,Right)＞
 Private Sub MergeSort(ByRef arr As Variant, ByVal left As Long, ByVal right As Long) 
    Dim mid As Long                            '中間点の計算ワーク                                         　
    Dim wka As String                          'マージ結果の内容を表示するワーク  
　  Dim ix1 As Long    　
’
    If left < right Then                        'Left=right は１件のみなので終了
       mid = (left + right) / 2                 '中間点を計算（小数点以下切り捨て）
A:     Call MergeSort(arr, left, mid)           '左側を再帰的に呼出し
B:     Call MergeSort(arr, mid + 1, right)      '右側を再帰的に呼出し
C:     Call Merge(arr, left, mid, right)        '左右を統合するMergeサブを呼出し
　　　 wka=""
 　　  for ix１＝Left to right
            wka=wka + str$(arr(ix1))
        next ix1
        debug.print wka                         '統合されたデータを確認のため印刷
  End If 
 End Sub

5.4　Mergeコード（VBA)

Mergeのコードです。指定範囲内のデータをソート後に元の配列に戻しています。
下記コードは昇順に並び替えています。

' ＜Merge（Arr,Left,Mid,Right)＞
Private Sub Merge(ByRef arr, ByVal left As Long, ByVal mid As Long, ByVal right As Long)
 Dim temp() As Long　　　　　　　　　　　　　　　'一時的な保存エリア
 Dim ixa As Long, ixb As Long, ixn As Long
 Dim ixc As Integer
 　ReDim temp(left To right)                     '使用する配列位置を定義 
 ixa = left                                      'ixa=左側の左端の位置
 ixb = mid + 1　　　　　　　　　　　 　          'ixb=右側の左端の位置
 ixn = left                                      'tempに保存する位置
'
 Do While ixa <= mid Or ixb <= right             'ixaが中間点まで又はixbが右端までの間実行
 If ixa > mid Then                               'ixaが中間点を超えた
     temp(ixn) = arr(ixb)　　　　　　　　            '右側のデータを保存
     ixb = ixb + 1                                   '右側の位置を次へ移動
 Else                                         　 'ixaが中間点に達していない
     If ixb > right Then　　　　　　　　      　     'ixbが右端の位置を超えた
         temp(ixn) = arr(ixa)                            '左側のデータを保存
         ixa = ixa + 1                                   '左側の位置を次へ移動
     Else                                            'ixbが右端に達していない
         If arr(ixa) <= arr(ixb) Then　　　　  　        '左側のデータ<=右側のデータ
             temp(ixn) = arr(ixa) 　　　　　　　             '左側を保存して次へ 
             ixa = ixa + 1                                   '左側の位置を次へ移動
         Else                                            '左側のデータ>右側のデータ
             temp(ixn) = arr(ixb)                            '右側を保存して次へ
             ixb = ixb + 1                                   '右側の位置を次へ移動
         End If
     End If
 End If
 ixn = ixn + 1                                   '保存位置を次へ移動 
 Loop
'
'元の配列に戻す
 For ixc = left To right
     arr(ixc) = temp(ixc)　　　　　　　　　　　　　
 Next ixc
End Sub