|Title||Sort an array with the mergesort algorithm|
|Description||This 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.|
|Keywords||mergesort, sort, array, CopyMemory, RtlMoveMemory, MoveMemory|
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
' 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)) _
' The smaller value is in the first half.
list(counterMain) = temp_array(counterA)
counterA = counterA + 1
' The smaller value is in the second half.
list(counterMain) = temp_array(counterB)
counterB = counterB + 1
counterMain = counterMain + 1
' Copy any remaining items from the first half.
If counterA <= middle Then
CopyMemory list(counterMain), temp_array(counterA), _
(middle - counterA + 1) * Len(list(beginning))
' Copy any remaining items from the second half.
If counterB <= ending Then
CopyMemory list(counterMain), temp_array(counterB), _
(ending - counterB + 1) * Len(list(beginning))
See my book Ready-to-Run Visual Basic Algorithms, Second Edition for more information on this and other sorting algorithms.