Click here to Skip to main content
Click here to Skip to main content

Tagged as

Go to top

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

, 29 Dec 2009
Rate this:
Please Sign up or sign in to vote.
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.

Merge Sort

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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

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

Comments and Discussions

 
Generalmemory consumption PinmemberChrist Kennedy29-Dec-09 10:21 
GeneralRe: memory consumption PinmemberMr. Fox29-Dec-09 21:36 
GeneralMy vote of 1 PinmemberOzgur Ozcitak29-Dec-09 9:36 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140905.1 | Last Updated 29 Dec 2009
Article Copyright 2009 by Ali Tarhini
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid