Here you will find two VB.NET implementations of a merge sort. The first essentially takes the pseudocode described previously and puts it into VB.NET syntax. The second includes a considerable enhancement in terms of space and time usage, and therefore performance.
Public Class Form1
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim myList(7) As Integer
myList(0) = 66
myList(1) = 44
myList(2) = 63
myList(3) = 8
myList(4) = 10
myList(5) = 12
myList(6) = 144
myList(7) = 106
Dim Listout() As Integer
Listout = MergeSort(myList)
Dim stOut As String
For i As Integer = 0 To UBound(Listout)
stOut = stOut & Listout(i) & vbNewLine
Next
MsgBox(stOut, , “Merge Sorted List”)
End Sub
Function MergeSort(Arr() As Integer) As Integer()
Dim ArrLeftHalf() As Integer
Dim ArrRightHalf() As Integer
If UBound(Arr) = 0 Then
Return Arr
Exit Function
Else
Call SplitList(Arr, ArrLeftHalf, ArrRightHalf)
ArrLeftHalf = MergeSort(ArrLeftHalf)
ArrRightHalf = MergeSort(ArrRightHalf)
Return MergeTwoLists(ArrLeftHalf, ArrRightHalf)
End If
End Function
Sub SplitList(Arr() As Integer, ByRef ArrLeft() As Integer, ByRef ArrRight() As Integer)
'Splits a list into two and returns the two resulting lists via parameters
Dim iMiddle As Integer = Math.Floor((LBound(Arr) + UBound(Arr)) / 2)
'Populate empty list with left half of original list
ReDim ArrLeft(iMiddle)
For i As Integer = 0 To iMiddle
ArrLeft(i) = Arr(i)
Next
'Populate empty list with right half of original list
Dim iFill As Integer
ReDim ArrRight(UBound(Arr) – UBound(ArrLeft) – 1)
For i As Integer = iMiddle + 1 To UBound(Arr)
ArrRight(iFill) = Arr(i)
iFill = iFill + 1
Next
End Sub
Function MergeTwoLists(Arr1() As Integer, Arr2() As Integer) As Integer()
'Merge two sorted lists into one sorted list
Dim Arr3() As Integer ‘Source lists will be merged into new list Arr3
ReDim Arr3(UBound(Arr1) + UBound(Arr2) + 1)
Dim Ptr1 As Integer
Dim Ptr2 As Integer
Dim Ptr3 As Integer
'Repeat until one of the arrays is exhausted
Do While (Ptr3 <= UBound(Arr3)) And (Ptr1 <= UBound(Arr1)) And (Ptr2 <= UBound(Arr2))
If Arr1(Ptr1) < Arr2(Ptr2) Then
Arr3(Ptr3) = Arr1(Ptr1)
Ptr1 = Ptr1 + 1
Else
Arr3(Ptr3) = Arr2(Ptr2)
Ptr2 = Ptr2 + 1
End If
Ptr3 = Ptr3 + 1
Loop
'Copy reamining items from larger of the source arrays into Arr3
If Ptr1 <= UBound(Arr1) Then 'still some items in Arr1
Do Until Ptr3 = UBound(Arr3) + 1
Arr3(Ptr3) = Arr1(Ptr1)
Ptr1 = Ptr1 + 1
Ptr3 = Ptr3 + 1
Loop
ElseIf Ptr2 <= UBound(Arr2) Then 'still some items in Arr2
Do Until Ptr3 = UBound(Arr3) + 1
Arr3(Ptr3) = Arr2(Ptr2)
Ptr2 = Ptr2 + 1
Ptr3 = Ptr3 + 1
Loop
End If
Return Arr3
End Function
End Class
Although the implementation above is indeed a working merge sort, there is something rather clumsy about it. The issue lies within the SplitList procedure. Whenever we split an array into two, that is, whenever we split a portion of the original array into two, we create two new arrays, and physically copy data into these two arrays. Then we merge pairs of temporary arrays to create yet another temporary array. Copying data around like this is an expensive process, particularly since we are doing it over and over and we don’t have any intention of hanging onto the intermediate arrays that are generated. Merge sort is often used to sort very large data sets, so we need to be mindful of how we use the memory. The fact is, we don’t ever realy need to split an array into two; we just need to achieve the effect of doing so. Our code just needs to look at the appropriate portion of the original array. This can be achieved by means of a few pointers.
Public Class Form1
Private Sub Button1_Click(sender As Object, e As EventArgs) Handles Button1.Click
Dim myList(7) As Integer
myList(0) = 66
myList(1) = 44
myList(2) = 63
myList(3) = 8
myList(4) = 10
myList(5) = 12
myList(6) = 144
myList(7) = 106
MergeSort(myList, LBound(myList), UBound(myList))
Dim stOut As String
For i As Integer = 0 To UBound(myList)
stOut = stOut & myList(i) & vbNewLine
Next
MsgBox(stOut, , “Merge Sorted List”)
End Sub
Function MergeSort(ByRef Arr As Integer(), iLow As Integer, iHigh As Integer)
'Pointers are then modified with successive calls, to redefine the portion being worked on.
If iLow >= iHigh Then
Return True
Else
Dim iMiddle As Integer = iLow + (iHigh – iLow) \ 2
Call MergeSort(Arr, iLow, iMiddle) 'left half is iLow to iMiddle
Call MergeSort(Arr, iMiddle + 1, iHigh) 'right half is iMiddle + 1 to iHigh
Call Merge(Arr, iLow, iMiddle, iHigh)
End If
End Function
Sub Merge(ByRef Arr As Integer(), iLow As Integer, iMiddle As Integer, iHigh As Integer)
'Performs a merge in place; original array is the target
'Values of iLow, iMiddle and iHigh define which two sections of the original to ‘merge’
Dim uLeft As Integer = iMiddle – iLow 'Calculate upper bound of left portion
Dim uRight As Integer = iHigh – iMiddle – 1 'Calculate upper bound of right portion
'Set up temporary source arrays to merge together
Dim ArrLeftHalf As Integer()
Dim ArrRightHalf As Integer()
ReDim ArrLeftHalf(iMiddle – iLow)
ReDim ArrRightHalf(iHigh – iMiddle – 1)
Dim Ptr1 As Integer, Ptr2 As Integer, Ptr3 As Integer
'Generate temporary left half
For Ptr1 = 0 To uLeft
ArrLeftHalf(Ptr1) = Arr(iLow + Ptr1)
Next
'Generate temorary right half
For Ptr2 = 0 To uRight
ArrRightHalf(Ptr2) = Arr(iMiddle + 1 + Ptr2)
Next
Ptr1 = 0
Ptr2 = 0
Ptr3 = iLow 'scan target from a position that leaves sorted data in tact
'Repeat until one of the source arrays is exhausted
While (Ptr1 <= uLeft) And (Ptr2 <= uRight)
If ArrLeftHalf(Ptr1) < ArrRightHalf(Ptr2) Then
Arr(Ptr3) = ArrLeftHalf(Ptr1)
Ptr1 = Ptr1 + 1
Else
Arr(Ptr3) = ArrRightHalf(Ptr2)
Ptr2 = Ptr2 + 1
End If
Ptr3 = Ptr3 + 1
End While
'Copy reamining items from larger of the source arrays into target array
While Ptr1 <= uLeft 'still some items in the left half
Arr(Ptr3) = ArrLeftHalf(Ptr1)
Ptr1 = Ptr1 + 1
Ptr3 = Ptr3 + 1
End While
While Ptr2 <= uRight 'still some items in the right half
Arr(Ptr3) = ArrRightHalf(Ptr2)
Ptr2 = Ptr2 + 1
Ptr3 = Ptr3 + 1
End While
End Sub
End Class