Merge Sorting Algorithm in C#

Merge sort is based on the divide-and-conquer paradigm. Its worst-case running time has a lower order of growth than insertion sort. Since we are dealing with sub problems, we state each sub problem as sorting a subarray A[p .. r]. Initially, p = 1 and r = n, but these values change as we recurse through sub problems.

Algorithm: Merge Sort

To sort the entire sequence A[1 .. n], make the initial call to the procedure MERGE-SORT (A, 1, n).

MERGE-SORT (A, p, r)

1. IF p < r // Check for base case
2. THEN q = FLOOR[(p + r)/2] // Divide step
3. MERGE (A, p, q) // Conquer step.
4. MERGE (A, q + 1, r) // Conquer step.
5. MERGE (A, p, q, r) // Conquer step.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

 

namespace MergeSort

{

    class MergeSort

    {

        static public void MainMerge(int[] numbers, int left, int mid, int right)

        {

            int[] temp = new int[25];

            int i, eol, num, pos;

 

            eol = (mid - 1);

            pos = left;

            num = (right - left + 1);

 

            while ((left <= eol) && (mid <= right))

            {

                if (numbers[left] <= numbers[mid])

                    temp[pos++] = numbers[left++];

                else

                    temp[pos++] = numbers[mid++];

            }

 

            while (left <= eol)

                temp[pos++] = numbers[left++];

 

            while (mid <= right)

                temp[pos++] = numbers[mid++];

 

            for (i = 0; i < num; i++)

            {

                numbers[right] = temp[right];

                right--;

            }

        }

 

        static public void SortMerge(int[] numbers, int left, int right)

        {

            int mid;

 

            if (right > left)

            {

                mid = (right + left) / 2;

                SortMerge(numbers, left, mid);

                SortMerge(numbers, (mid + 1), right);

 

                MainMerge(numbers, left, (mid + 1), right);

            }

        }

 

        static void Main(string[] args)

        {

 

            Console.Write("\nProgram for sorting a numeric array using Merge Sorting");

            Console.Write("\n\nEnter number of elements: ");

            int max = Convert.ToInt32(Console.ReadLine());

            int[] numbers = new int[max];

            for (int i = 0; i < max; i++)

            {

                Console.Write("\nEnter [" + (i + 1).ToString() + "] element: ");

                numbers[i] = Convert.ToInt32(Console.ReadLine());

            }

            Console.Write("Input int array : ");

            Console.Write("\n");

            for (int k = 0; k < max; k++)

            {

                Console.Write(numbers[k] + " ");

                Console.Write("\n");

            }

            Console.WriteLine("MergeSort By Recursive Method");

            SortMerge(numbers, 0, max - 1);

            for (int i = 0; i < max; i++)

                Console.WriteLine(numbers[i]);

            Console.ReadLine();

        }

    }

}