マージソートのサンプルコード

VBAの勉強会で話題に上がった「マージソート」を実装してみたので、サンプルコードとしてブログに乗せておきます。

ExcelVBAでは、ワークシートに優秀なソート・フィルター機能がついているため、
実務において自分でソートプログラムを作って使うことはめったにありません。

このコードも実務で使うための工夫とかは一切しておらず、あくまでマージソートの手順を表現してみたただけですので、その前提でご参考ください。

マージソートとは

4,2,6,7,1,3,8,5 ⇒ 1,2,3,4,5,6,7,8

という並び替えをしたいとします。

この時、全通りの組み合わせを比較して並び替えると、
大体8×8=64通りの比較が必要になります。

ソートアルゴリズムの例としてよく出てくるバブルソートなどは、
この回数比較しているソートですね。
※ 本当は重複をなくして8×7÷2=27回で済みますが、話を単純化してただn×nとします。

さて、この64回の比較を減らして高速化しましょう。

まず、元の並びを何も考えず真っ二つに割って、
「4,2,6,7」と「1,3,8,5」に分割します。

そしてこの二つを、それぞれ「総当たり」で並び替えます。

4,2,6,7 ⇒　2,4,6,7
1,3,8,5 ⇒　1,3,5,8

ここまでの比較回数は、4×4=16を2回で、計32回ですね。
（これも本当は4×3/2でできますが同じく話を単純にしてn×nで）

そのあとで、2,4,6,7 と 1,3,5,8を、並び替えながらくっつけます。

くっつける際「両方のブロックが並び替え済み」という性質を利用すると、
「両方のブロックの先頭同士を比較するだけで次の数字を持ってこれる」
という特徴があります。

例：一つ目の数字は「2と1」の小さい方で「1」
　　二つ目の数字は「2と3」の小さい方で「2」　…

ということで、比較1回で必ず1つの数字を確定できるので、
比較回数は8回で済みます。

これで、2,4,6,7 ＋ 1,3,5,8　⇒　1,2,3,4,5,6,7,8
の並び替えが完了しますが、比較回数は

「ブロックの並び替え16回×2＋2ブロックのマージ8回= 40回」

で済みます。

総当たり形式よりだいぶ早く処理が終わりましたね！

というのがマージソートの原理（の半分）です。

一気にすべてを総当たりで比較するのではなく、
2個に割ってから総当たりをして、そのあと合体(マージ)した方が、
総当たりをする空間を小さくできて、結果的に早くなるということです。

※ これを「分割統治法」と呼びます。

さてこれがマージソートの原理「の半分」といいましたが、
じゃあもう半分はどこかというと、

まず、元の並びを何も考えず真っ二つに割って、
「4,2,6,7」と「1,3,8,5」に分割します。
そしてこの二つをそれぞれ「総当たり」で並び替えます。

↑この部分をもっと短縮できます。

どうやるかというと、すごく単純な話で、

まず、元の並びを何も考えず真っ二つに割って、
「4,2,6,7」と「1,3,8,5」に分割します。
そしてこの二つをそれぞれ「マージソート」で並び替えます。

に変えればいいということです。

分割した2つのブロックをそれぞれ並び替えるのにも、
マージソートを使えばいいのです。

「4,2,6,7」を「4,2」と「6,7」に分けて同じことをするということですね。

そうすると、この「4,2」も「4」と「2」分割して～～と、
最後は要素が1個になるまでマージソートの中でマージソート
をしていくことになります。

このように、ある処理の中でその処理をマトリョーシカみたいに使っていくことを、
プログラミング用語で「再帰呼び出し」といいます。

マージソートは「再帰呼び出し」を使って実装しますので、
再帰を使うコードの参考にしてみてください。

（と、偉そうに言うほど私はアルゴリズムを勉強していませんのでありからず）

ソースコード

' ◆ マージソート(再帰)
Function マージソート(元配列) As Variant

    ' 要素1はソート済みとしてそのまま返す（再帰的にはここで分割が終了）
    If UBound(元配列) = 0 Then
        マージソート = 元配列
        Exit Function
    End If
    
    ' ■ 配列を左右に2分割
    Dim 分割配列L, 分割配列R
    Call 配列を2つに分割する(元配列, 分割配列L, 分割配列R)
    
    ' ◆ 分割した配列それぞれをマージソート（再帰）
    分割配列L = マージソート(分割配列L)
    分割配列R = マージソート(分割配列R)

    ' ▲ ソート済になった2つ配列を、1つの配列にマージして返す
    マージソート = ソート済みの2配列をマージする(分割配列L, 分割配列R)

End Function

' ■ 分割
Private Sub 配列を2つに分割する(元配列, Res配列L, Res配列R)

    Dim 分割位置 As Long: 分割位置 = (UBound(元配列)) \ 2
    
    Res配列L = 配列の指定区間を抽出する(元配列, 0, 分割位置)
    Res配列R = 配列の指定区間を抽出する(元配列, 分割位置 + 1, UBound(元配列))
    
    ' Debug.Print Join(Res配列L, ",") & " / " & Join(Res配列R, ",")
End Sub

Private Function 配列の指定区間を抽出する(元配列, i1st As Long, iLast As Long) As Variant

    ReDim Res配列(0 To iLast - i1st)
    Dim i As Long
    For i = 0 To iLast - i1st
        Res配列(i) = 元配列(i1st + i)
    Next
    
    配列の指定区間を抽出する = Res配列
End Function


' ▲ マージ
Private Function ソート済みの2配列をマージする(配列1, 配列2) As Variant

    Dim i1 As Long, i2 As Long, i As Long
    Dim i1Last As Long: i1Last = UBound(配列1)
    Dim i2Last As Long: i2Last = UBound(配列2)

    Dim Res配列
    ReDim Res配列(0 To i1Last + i2Last + 1)
    Dim iRes As Long

    Do
        ' どちらかの配列が枯れたらもう一方をすべて出力してExit
        If i1 > i1Last Then
            For i = i2 To i2Last
                Res配列(iRes) = 配列2(i)
                iRes = iRes + 1
            Next
            Exit Do
            
        ElseIf i2 > i2Last Then
            For i = i1 To i1Last
                Res配列(iRes) = 配列1(i)
                iRes = iRes + 1
            Next
            Exit Do
        
        ' 両配列を見て値が小さい方を結果配列へ
        Else
            If 配列1(i1) <= 配列2(i2) Then ' ←この等号が安定ソートに必要
                Res配列(iRes) = 配列1(i1)
                i1 = i1 + 1
            Else
                Res配列(iRes) = 配列2(i2)
                i2 = i2 + 1
            End If
            iRes = iRes + 1
        End If
        
    Loop
    
    ソート済みの2配列をマージする = Res配列
    ' Debug.Print Join(配列1, ",") & " + " & Join(配列2, ","); " ⇒ " & Join(Res配列, ",")
End Function

実行例

コード内でコメントアウトしている「Debug.Print」の、
先頭の'を消して(コメントインして)実行すると、
マージソートの手順「分割」「マージ」の様子が記録されるようにしてみました。

ソート済み配列 = マージソート(array(4,2,6,7,1,3,8,5))

と、サンプルで説明した4,2,6,7,1,3,8,5を並び替えてみると、
以下のように関数が再帰呼出されているのがわかりますので、
コードを読み解く際の手掛かりにしてみてください。

4,2,6,7 / 1,3,8,5
4,2 / 6,7
4 / 2
4 + 2 ⇒ 2,4
6 / 7
6 + 7 ⇒ 6,7
2,4 + 6,7 ⇒ 2,4,6,7
1,3 / 8,5
1 / 3
1 + 3 ⇒ 1,3
8 / 5
8 + 5 ⇒ 5,8
1,3 + 5,8 ⇒ 1,3,5,8
2,4,6,7 + 1,3,5,8 ⇒ 1,2,3,4,5,6,7,8

おまけ：自分なりに理解に時間がかかったところ

昔このコードを書こうとしたとき、

「そもそも分割を再帰で順次にするのはなんで？」
「最初から1個ずつになってる状態でスタートすればいいじゃん」

という疑問に答えが出せず、自力では組めなかった思い出があります。

↑この疑問の回答としては、
「分割と結合を同じ関数内で行うことで、きれいに2等分している」
ということなんですね。

例えば70個の配列をソートするとき、
1→2→4→8 とバラバラの状態から2倍2倍とマージしていくと、
最後のマージが64＋6といびつなマージになってしまいます。

対してちゃんと分割→分割→1個になったら→結合→結合
という手順を踏むと、

70個 → 35個 35個 → 18個 17個 18個 17個 → …

と、2等分しながら進めるため、最後のマージも35個＋35個で、
理想的に高速化できるということなんですね。

同じ疑問を抱く方がどのくらいいるかわかりませんが、
参考までにおいておきます。

こういったソート系の実装に昔はものすごく苦戦して、
それ以来ソートの自作はしていませんでした。

しかし、VBAをちゃんと勉強した今組んでみたら、
案外行けたので結構嬉しかったですね。

あれだけ強かったタケシやカスミも今戦ったら勝てる的な。

みなさんもそんなボスに心当たりがあれば戦ってみてください。

今ならヒトカゲを選んでも大丈夫でしょうし、
自分の成長を実感できるんじゃないかなと思います(´∀｀)