Search - Articles
DevASP.NET for ASP.NET, VB.NET, XML and C# (C-Sharp) Developers Tuesday, March 03, 2009
Dev Articles
Search Directory
ASP.NET
VB.Net
C-Sharp
SQL Server
 

How to do Sorting using Merge Sort algorithm in C# (.net 2.0)

Author: Zunnair
Download Source Code : 859_sort.zip

In this simple article you will learn how to do sorting using Merge sort in VB and C# .net 2.0.

 

Merge sort is one of the fastest sorting algorithms. This algorithm belongs to merging category of sorting algorithms.
How Merge sort works:
This algorithm uses an array breaking technique. It breaks the array into half and gets two arrays, sort those halves and than break them in to their halves and sort them, it continues this process till there does not remain a one element in each divided array. After that it merges these arrays with same order in which it broke the array. For this purpose merge sort uses a recursive functions. Every time when function is called you have to send start, mid and end of array.
Complexity of Merge Sort Algorithm:
This algorithm takes n log n time in its worst and average case. So we can say that its complexity is BIG O of n log n.
.
To demonstrate this make a window form based application. Drag one button and one list box on the form. Load an integer array in the list box and than press button to sort.
Now write the following code on Button Click event:
C#
private void btn_Sort_Click(object sender, EventArgs e)
        {
            MergeSort(0,4);
            listBox_elements.Items.Clear();
            for (int x = 0; x < arr.Length; x++)
                listBox_elements.Items.Insert(x, arr.GetValue(x));
        }
VB
Private Sub btn_Sort_Click(ByVal sender As Object, ByVal e As EventArgs)
        MergeSort(0,4);
        listBox_elements.Items.Clear()
        For x As Integer = 0 To arr.Length - 1
            listBox_elements.Items.Insert(x, arr.GetValue(x))
        Next
    End Sub
This is a simple code to call Merge Sort () Function. After sorting, this code will load the sorted array in list box.
Now write the following code in Merge Sort () Function:
C#
private void MergeSort(int left,int right)
        {
            int mid = (left + right) / 2;
              if (left < right) {
                  MergeSort(left, mid);
                  MergeSort(mid + 1, right);
                merge(left, mid, right);
              }
        }
VB
Private Sub MergeSort(ByVal left As Integer, ByVal right As Integer)
        Dim mid As Integer = (left + right) / 2
       If left < right Then
            MergeSort(left, mid)
            MergeSort(mid + 1, right)
            merge(left, mid, right)
 
        End If
    End Sub
C#
private void merge(int left,int mid,int right)
        {
            int y = 0, z = 0;
            int leftno = mid - left + 1;
            int rightno = right - mid;
            int[] obj1 = new int[leftno];
            int[]obj2 = new int[rightno];
 
            for (y = 0; y < leftno; y++)
            {
                obj1.SetValue(arr.GetValue(left + y),y);
             }
            for (z = 0; z < rightno; z++)
            {
                obj2.SetValue(arr.GetValue(mid + z + 1),z);
            }
            y = 0;
            z = 0;
 
            for (int i = left; i <= right; i++)
            {
                if ((y < leftno) && (z < rightno))
                {
                    if ((int)obj1.GetValue(y) <= (int)obj2.GetValue(z))
                    {
                        arr.SetValue(obj1.GetValue(y),i);
                        y++;
                    }
                    else
                    {
                        arr.SetValue(obj2.GetValue(z), i);
                        z++;
                    }
                }
                else if ((y < leftno) && (z >= rightno))
                {
                    arr.SetValue(obj1.GetValue(y), i);
                    y++;
                }
                else if ((y >= leftno) && (z < rightno))
                {
                    arr.SetValue(obj2.GetValue(z), i);
                    z++;
                }
 
            }
        }
VB
Private Sub merge(ByVal left As Integer, ByVal mid As Integer, ByVal right As Integer)
        Dim y As Integer = 0, z As Integer = 0
        Dim leftno As Integer = mid - left + 1
        Dim rightno As Integer = right - mid
        Dim obj1 As Integer() = New Integer(leftno - 1) {}
        Dim obj2 As Integer() = New Integer(rightno - 1) {}
 
        For y = 0 To leftno - 1
            obj1.SetValue(arr.GetValue(left + y), y)
        Next
        For z = 0 To rightno - 1
            obj2.SetValue(arr.GetValue(mid + z + 1), z)
        Next
        y = 0
        z = 0
 
        For i As Integer = left To right
            If (y < leftno) AndAlso (z < rightno) Then
                If CInt(obj1.GetValue(y)) <= CInt(obj2.GetValue(z)) Then
                    arr.SetValue(obj1.GetValue(y), i)
                    y += 1
                Else
                    arr.SetValue(obj2.GetValue(z), i)
                    z += 1
                End If
            ElseIf (y < leftno) AndAlso (z >= rightno) Then
                arr.SetValue(obj1.GetValue(y), i)
                y += 1
            ElseIf (y >= leftno) AndAlso (z < rightno) Then
                arr.SetValue(obj2.GetValue(z), i)
                z += 1
 
            End If
        Next
    End Sub
This is simple code to sort.
Now write the following code on FORM LOAD event:
C#
 private void Form1_Load(object sender, EventArgs e)
        {                 
            arr.SetValue(8, 0);
            arr.SetValue(9,1);
            arr.SetValue(2, 2);
            arr.SetValue(4, 3);
            arr.SetValue(7, 4);
            for (int i = 0; i < arr.Length; i++)
                listBox_elements.Items.Insert(i, arr.GetValue(i));
            this.Text = "DEVASP MERGE SORT APPLICATION";
 
        }
VB
Private Sub Form1_Load(ByVal sender As Object, ByVal e As EventArgs)
        Me.Text = "DEVASP MERGE SORT APPLICATION"
        arr.SetValue(8, 0)
        arr.SetValue(9, 1)
        arr.SetValue(2, 2)
        arr.SetValue(4, 3)
        arr.SetValue(7, 4)
        For i As Integer = 0 To arr.Length - 1
            listBox_elements.Items.Insert(i, arr.GetValue(i))
        Next
    End Sub
This simple article tells some how to do sorting using MERGE sort in VB and C# .net 2.0.
 

 

   
Add Article Comment:
Name :
Email Address :
   
Comments :
 
   
<< How to do Sorting using Shell Sort algorithm in C# (.net 2.0)

Disclaimer - Privacy
© 2002-2017 DevASP.net