12,064,782 members (31,458 online)
Merge sort is an O(n log n) comparison-based sorting algorithm, It was invented by John von Neumann in 1945. It is based on the divide-and-conquer paradigm and is used to sort large amounts of information. The original source of the article is taken from How To Implement Merge Sort in VB.NET
The Merge Sort Algorithm mainly consists of 3 steps. For the sake of explanation, let's assume we are dealing with arrays containing random digits that we would like to sort either ascending or descending:
Here is a picture take from http://en.wikipedia.org/wiki/Merge_sort graphing the behavior of merge sort on random data.
To implement merge sort in VB.NET is not quite an easy task, But... if you got the concept right then it won't be that tough. Below is the merge sort function written to sort an array of integers. Although you might find several different versions and many variations for the implementation of merge sort, this function is unique and is crafted in a special way to achieve IN-PLACE sorting, meaning that the original unsorted array will be replaced by the resulting sorted sequence, So no new array is formed thus minimizing memory consumption because as we said earlier, merge sort is used to sort large amounts of information so we need to take care about our memory limitations. Suppose we have an array of 32 bit integers (4 bytes) of length 180,000,000. The array size will be 703125KB or 686MB which is a considerable memory space. Assume our sorting algorithm creates a sorted array instead of replacing the existing one, then the total consumed space would be 1.34GB of RAM, A huge turndown for personal computer users!
Here is the
public method for calling merge sort passing in the array. Note that arrays in Visual Basic .NET are reference types, so ByVal and ByRef both mean the latter.
Public Sub MergeSort(ByVal ar() As Integer) DoMergeSort(ar, 0, ar.Length - 1) End Sub
The implementation of IN-PLACE merge sort:
Private Sub DoMergeSort(ByVal ar() As Integer, _ ByVal low As Integer, ByVal high As Integer) If low >= high Then Return Dim length As Integer = high - low + 1 Dim middle As Integer = Math.Floor((low + high) / 2) DoMergeSort(ar, low, middle) DoMergeSort(ar, middle + 1, high) Dim temp(ar.Length - 1) As Integer For i As Integer = 0 To length - 1 temp(i) = ar(low + i) Next Dim m1 As Integer = 0 Dim m2 As Integer = middle - low + 1 For i As Integer = 0 To length - 1 If m2 <= high - low Then If m1 <= middle - low Then If temp(m1) > temp(m2) Then ar(i + low) = temp(m2) m2 += 1 Else ar(i + low) = temp(m1) m1 += 1 End If Else ar(i + low) = temp(m2) m2 += 1 End If Else ar(i + low) = temp(m1) m1 += 1 End If Next End Sub