Ready-to-Run Visual Basic Algorithms

[nandagopal]

The mergesort algorithm divides an array into two equal pieces, sorts them recursively, and then merges them back together.

Subroutine MergeSort divides the array. It calls itself to sort the two halves and then calls subroutine Merge to recombine the halves.

Subroutine Merge recombines two sorted halves of an array. It starts by copying the halves into a temporary array. It then initializes two indexes to refer to the smallest item in each half of the temporary array. It picks the smaller of the two, moves it into the original output array, and increments its index.

The subroutine continues this process until one half of the temporary array has been completely moved. It then copies the rest of the other half into the original output array and it is done.

Note that this version uses the CopyMemory API function (aka RtlMoveMemory) to copy parts of the arrays quickly.


' Sort the list entries with indexes between beginning
' and ending.

Code Select Expand

Public Sub MergeSort(list() As Integer, ByVal first_index _
    As Long, ByVal last_index As Long)
Dim middle As Long

    If (last_index > first_index) Then
        ' Recursively sort the two halves of the list.
        middle = (first_index + last_index) \ 2
        MergeSort list, first_index, middle
        MergeSort list, middle + 1, last_index

        ' Merge the results.
        Merge list, first_index, middle, last_index
    End If
End Sub

' Merge two sorted sublists.
Public Sub Merge(list() As Integer, ByVal beginning As _
    Long, ByVal middle As Long, ByVal ending As Long)
Dim temp_array() As Integer
Dim temp As Integer
Dim counterA As Long
Dim counterB As Long
Dim counterMain As Long

    ' Copy the array into a temporary array.
    ReDim temp_array(beginning To ending)
    CopyMemory temp_array(beginning), list(beginning), _
        (ending - beginning + 1) * Len(list(beginning))

    ' counterA and counterB mark the next item to save
    ' in the first and second halves of the list.
    counterA = beginning
    counterB = middle + 1

    ' counterMain is the index where we will put the
    ' next item in the merged list.
    counterMain = beginning
    Do While (counterA <= middle) And (counterB <= ending)
        ' Find the smaller of the two items at the front
        ' of the two sublists.
        If (temp_array(counterA) <= temp_array(counterB)) _
            Then
            ' The smaller value is in the first half.
            list(counterMain) = temp_array(counterA)
            counterA = counterA + 1
        Else
            ' The smaller value is in the second half.
            list(counterMain) = temp_array(counterB)
            counterB = counterB + 1
        End If
        counterMain = counterMain + 1
    Loop

    ' Copy any remaining items from the first half.
    If counterA <= middle Then
        CopyMemory list(counterMain), temp_array(counterA), _
            (middle - counterA + 1) * Len(list(beginning))
    End If

    ' Copy any remaining items from the second half.
    If counterB <= ending Then
        CopyMemory list(counterMain), temp_array(counterB), _
            (ending - counterB + 1) * Len(list(beginning))
    End If
End Sub