[Squirm]

Merge Sort
At a first glance the merge sort appears to be identical to the quick sort. However, rather than separating the values into distinct left and right groups, we simply sort them straight away with no pivot values. The value comparisons are done when we come to merge the two sorts together, but since the groups are ordered, we need only compare the smallest of one group with the smallest of the other.

Example:

Array of data [2,8,4,9,3,5,7,1,0,6]

       [2,8,4,9,3,5,7,1,0,6]
         |               |             Recursive step
   [2,8,4,9,3]       [5,7,1,0,6]
    |       |         |       |        Recursive step
  [2,8]  [4,9,3]    [5,7]  [1,0,6]
    |     |   |       |     |   |      Recursive step
  [2,8]  [4][3,9]   [5,7]  [1][0,6]
    |     |   |       |     |   |      Merge step
  [2,8]  [3,4,9]    [5,7]  [0,1,6]
    |       |         |       |        Merge step
   [2,3,4,8,9]       [0,1,5,6,7]
         |               |             Merge step
       [0,1,2,3,4,5,6,7,8,9]

Finish [0,1,2,3,4,5,6,7,8,9]

The merge sort is different in other ways. For one, it requires a second array to hold the data, as we merge from one into the other. Another difference is that it can easily be implemented non-recursively, as I have done in the code below. The MergeSort procedure calls the InnerMergePass sub with larger and larger segment sizes.

Public Sub MergeSort(ByRef lngArray() As Long)
    Dim arrTemp() As Long
    Dim iSegSize As Long
    Dim iLBound As Long
    Dim iUBound As Long
    
    iLBound = LBound(lngArray)
    iUBound = UBound(lngArray)
        
    ReDim arrTemp(iLBound To iUBound)
    
    iSegSize = 1
    Do While iSegSize < iUBound - iLBound
        
        'Merge from A to B
        InnerMergePass lngArray, arrTemp, iLBound, iUBound, iSegSize
        iSegSize = iSegSize + iSegSize
        
        'Merge from B to A
        InnerMergePass arrTemp, lngArray, iLBound, iUBound, iSegSize
        iSegSize = iSegSize + iSegSize
        
    Loop
End Sub

Private Sub InnerMergePass(ByRef lngSrc() As Long, ByRef lngDest() As Long, ByVal iLBound As Long, iUBound As Long, ByVal iSegSize As Long)
    Dim iSegNext As Long
    
    iSegNext = iLBound
    
    Do While iSegNext <= iUBound - (2 * iSegSize)
        'Merge 2 segments from src to dest
        InnerMerge lngSrc, lngDest, iSegNext, iSegNext + iSegSize - 1, iSegNext + iSegSize + iSegSize - 1
        
        iSegNext = iSegNext + iSegSize + iSegSize
    Loop
    
    'Fewer than 2 full segments remain
    If iSegNext + iSegSize <= iUBound Then
        '2 segs remain
        InnerMerge lngSrc, lngDest, iSegNext, iSegNext + iSegSize - 1, iUBound
    Else
        '1 seg remains, just copy it
        For iSegNext = iSegNext To iUBound
            lngDest(iSegNext) = lngSrc(iSegNext)
        Next iSegNext
    End If

End Sub

Private Sub InnerMerge(ByRef lngSrc() As Long, ByRef lngDest() As Long, ByVal iStartFirst As Long, ByVal iEndFirst As Long, ByVal iEndSecond As Long)
    Dim iFirst As Long
    Dim iSecond As Long
    Dim iResult As Long
    Dim iOuter As Long
    
    iFirst = iStartFirst
    iSecond = iEndFirst + 1
    iResult = iStartFirst
    
    Do While (iFirst <= iEndFirst) And (iSecond <= iEndSecond)
    
        'Select the smaller value and place in the output
        'Since the subarrays are already sorted, only one comparison is needed
        If lngSrc(iFirst) <= lngSrc(iSecond) Then
            lngDest(iResult) = lngSrc(iFirst)
            iFirst = iFirst + 1
        Else
            lngDest(iResult) = lngSrc(iSecond)
            iSecond = iSecond + 1
        End If
        
        iResult = iResult + 1
    Loop
    
    'Take care of any leftover values
    If iFirst > iEndFirst Then
        'Got some leftover seconds
        For iOuter = iSecond To iEndSecond
            lngDest(iResult) = lngSrc(iOuter)
            iResult = iResult + 1
        Next iOuter
    Else
        'Got some leftover firsts
        For iOuter = iFirst To iEndFirst
            lngDest(iResult) = lngSrc(iOuter)
            iResult = iResult + 1
        Next iOuter
    End If
End Sub