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

- 28
^{th} December, 2009: Initial post