CopyPastehas never been so tasty!

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);

         Console.ReadLine();

        }

        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("");

 

        }

  

    }

Add A Comment: