13,594,656 members
alternative version

#### Stats

34.4K views
7 bookmarked
Posted 29 Dec 2009
Licenced CPOL

# Sorting Algorithms in VB.NET: How To Implement Merge Sort

, 29 Dec 2009
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

## Introduction

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

## Background

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:

• Divide Step If an array has zero or one element, then it is already sorted. Otherwise, split the array into two arrays each containing about half of the elements of the parent array.
• Recursion Step Repeatedly divide child arrays until all child arrays have one element.
• Conquer Step Combine child elements back by merging them together into a bigger sorted sequence. Continue to merge up until there are no more child arrays to merge.

Here is a picture take from http://en.wikipedia.org/wiki/Merge_sort graphing the behavior of merge sort on random data.

## Using the Code

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```

## History

• 28th December, 2009: Initial post

## Share

 Software Developer (Senior) Microgen Lebanon
For more articles and extreme topics please check out my personal website www.alitarhini.com

## You may also be interested in...

 First Prev Next
 My vote of 1 duvver15-Oct-14 3:39 duvver 15-Oct-14 3:39
 memory consumption Christ Kennedy29-Dec-09 10:21 Christ Kennedy 29-Dec-09 10:21
 Re: memory consumption Mr. Fox29-Dec-09 21:36 Mr. Fox 29-Dec-09 21:36
 My vote of 1 Ozgur Ozcitak29-Dec-09 9:36 Ozgur Ozcitak 29-Dec-09 9:36
 Last Visit: 31-Dec-99 18:00     Last Update: 21-Jun-18 16:40 Refresh 1