# Merge Sort in c#

by anonymous

• 0
• 0
• 0
85 views
```Orignal Source:http://codingvilla.com/merge-sort-csharp-single-article-623.aspx

Merge Sort

Merge sort is efficient to use when you have enough memory because it takes two different sorted arrays and create a third array which contains all the elements of two arrays in sorted order.

How MergeSort Works

To see how merge sort works let’s examine two unsorted arrays

1  5  7  9  and

2  3  6  8

To merge them we examine first element of each array and choose the smaller. Here 1 < 2 so place 1 in the third(merged) list and move to the next index of first list

1  5  7  9          2  3  6  8

1

Now we compare 5 and 2. As 2 < 5 then 2 will be placed in the third list

1  5  7  9          2  3  6  8

1   2

We continue in this way until we get complete third(merged) list as:

1  5  7  9          2  3  6  8

1 2  3  4  5  6  7  8  9

The algorithm for the merge list as follows:

public static void merge(int[] arrayA, int sizeA, int[] arrayB, int sizeB, int[] arrayC)
{
int Ax = 0, Bx = 0, Cx = 0;
while (Ax < sizeA && Bx < sizeB)
if (arrayA[Ax] < arrayB[Bx])
arrayC[Cx++] = arrayA[Ax++];
else
arrayC[Cx++] = arrayB[Bx++];
while (Ax < sizeA)
arrayC[Cx++] = arrayA[Ax++];
while (Bx < sizeB)
arrayC[Cx++] = arrayB[Bx++];

}

The first while loop compares the element, find smaller and then place it in third array. The second while loop checks that if all the elements from array B have settled in Array C but Array A has still remaining elements. This loop will simply copy the remaining elements of Array A into Array C. The third loop checks if all the elements from Array A have transferred into Array C butt Array B has still remaining elements. This loop will simply copy the remaining elements of Array B into Array C.

Its complexity is O(n X logn).

The following sample code will show the sorting of arrays with the help of merge sort.

Code

class Program
{
static void Main(string[] args)
{
int[] arrayA = { 23, 47, 81, 95 };
int[] arrayB = { 7, 14, 39, 55, 62, 74 };
int[] arrayC = new int[10];

Program.merge(arrayA, 4, arrayB, 6, arrayC);
Program.show(arrayC, 10);
}
public static void merge(int[] arrayA, int sizeA, int[] arrayB, int sizeB,
int[] arrayC)
{

int Ax = 0, Bx = 0, Cx = 0;
while (Ax < sizeA && Bx < sizeB)
if (arrayA[Ax] < arrayB[Bx])
arrayC[Cx++] = arrayA[Ax++];
else
arrayC[Cx++] = arrayB[Bx++];
while (Ax < sizeA)
arrayC[Cx++] = arrayA[Ax++];
while (Bx < sizeB)
arrayC[Cx++] = arrayB[Bx++];

}
public static void show(int[] theArray, int size)
{
for (int j = 0; j < size; j++)
Console.WriteLine(theArray[j] + " ");
Console.WriteLine("");

}

}
```