Home
Search
 
What's New
Index
Books
Links
Q & A
Newsletter
Banners
 
Feedback
Tip Jar
 
C# Helper...
 
XML RSS Feed
Follow VBHelper on Twitter
 
 
 
MSDN Visual Basic Community
 
 
 
 
 
 
TitleSort an array with the mergesort algorithm
DescriptionThis example shows how to sort an array with the mergesort algorithm in Visual Basic 6. See my book "Ready-to-Run Visual Basic Algorithms" for more information on this and other sorting algorithms.
Keywordsmergesort, sort, array, CopyMemory, RtlMoveMemory, MoveMemory
CategoriesAlgorithms
 
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.
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
 
See my book Ready-to-Run Visual Basic Algorithms, Second Edition for more information on this and other sorting algorithms.
 
 
Copyright © 1997-2010 Rocky Mountain Computer Consulting, Inc.   All rights reserved.
  Updated