Merge Sort in C#

Merge sort is an algorithm which is based on divide and conquer, in this sorting we divide elements into 2 half, until we cannot divide it further and then sort the elements of an array, so in this article, I have mentioned how to implement Code for Merge Sort in C# with console application example.

The basic steps of a merge sort algorithm are as follows:

• If the array is of length 0 or 1, it is already sorted.
• Otherwise, divide the unsorted array into two sub-arrays of about half the size.
• Use the merge sort algorithm recursively to sort each sub-array. 
• Merge the two sub-arrays to form a single sorted list.

Merge Sort C# Code

Let's take a look at the merge sort C# program, in which will create an unsorted array and then create 2 methods

• one is merge method which combines the sub-arrays and another method mergeSort which divides the list into smaller units

using System;

namespace MergeSortCsharp
{
    public class Program
    {
        static void Main(string[] args)
        {
            int[] arr = { 44,55,66,11,22,99,88,77 };
            int n = 8, i;
            Console.WriteLine("-----Merge Sort-----");
            Console.WriteLine();
            Console.WriteLine("Initial array is: ");
            for (i = 0; i < n; i++)
            {
                Console.Write(arr[i] + " ");
            }
            mergeSort(arr, 0, n - 1);
            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine("After sorting array is: ");
            for (i = 0; i < n; i++)
            {
                Console.Write(arr[i] + " ");
            }
            Console.WriteLine();
            Console.WriteLine();
        }

        public static void merge(int[] arr, int beg, int mid, int end)
        {
            int i = beg, j = mid + 1, index = beg, k;
            int[] temp = new int[8];
            while ((i <= mid) && (j <= end))
            {
                if (arr[i] < arr[j])
                {
                    temp[index] = arr[i];
                    i++;
                }
                else
                {
                    temp[index] = arr[j];
                    j++;
                }
                index++;
            }
            if (i > mid)
            {
                while (j <= end)
                {
                    temp[index] = arr[j];
                    j++;
                    index++;
                }
            }
            else
            {
                while (i <= mid)
                {
                    temp[index] = arr[i];
                    i++;
                    index++;
                }
            }
            for (k = beg; k < index; k++)
                arr[k] = temp[k];
        }


        public static void mergeSort(int[] arr, int beg, int end)
        {
            int mid;
            if (beg < end)
            {
                mid = (beg + end) / 2;
                mergeSort(arr, beg, mid);
                mergeSort(arr, mid + 1, end);
                merge(arr, beg, mid, end);
            }
        }

    }
}

The output of the above program will be

-----Merge Sort-----

Initial array is:
44 55 66 11 22 99 88 77

After sorting array is:
11 22 44 55 66 77 88 99

The running time of merge sort in the average case and the worst case can be given as O(n log n).

Although merge sort has an optimal time complexity, it needs an additional O(n) space for the temporary array TEMP.

Merge sort can be useful when you are sorting small lists, as the number of steps is relatively less, thus less time is needed to create a sorted list.

You may also like to read:

System.Text.Json Serialize / Deserialize Object in C#

Creating Multi-Line String in Javascript

C# Split String into array

Merge sort algorithm in C with Program sample