Sorting Algorithms in C# - Merge Sort

In our journey of exploring the sorting algorithms in C#, Merge sort is one of the most powerful and elegant algorithm that implements the divide and conquer strategy in programming. Unlike the repetitive iteration approach the bubble sort and selection sort use, the Merge sort algorithm continuously divides the array into smaller sub-arrays until they are sorted.

Finally, it merges all the sub-arrays together forming a sorted array. Its consistent performance makes it a valuable algorithm for the aspiring C# developers. Therefore, we will learn this algorithm in this article.

Merge Sort: Divide and Conquer Strategy

At its core, the Merge sort algorithm follows the divide and conquer rule that has three steps:
1. Divide: The input array is divided into ideally equal halves. This division continues unless the sub-arrays contain only 1 element that is inherently sorted.
2. Conquer: The sub arrays containing 1 element are considered sorted.
3. Merge (Combine): The sorted sub arrays are combined together to produce the larger and sorted sub-arrays. The merging is continues unless the original sorted array is not formed.

Demonstration

Now that we have learned about the working principle of the merge sort, let’s break it down into step-by-step demonstration for further understanding. Let’s consider an unsorted array [2, 4, 1, 6, 5, 7]. The merge sort array will sort it as follows:
Divide
• The array is divided into 2 halves i.e. [2, 4, 1] and [6, 5, 7].
• The [2, 4, 1] is further divided into [2, 4] and [1] and [6, 5, 7] into [6, 5] and [7].
• The [2, 4] is again divided into [2] and [4] and [6, 5] to [6] and [5].
Now we have sub-arrays of size 1 that are considered sorted: [1], [7], [2], [4], [6], [5].

Step 2: Conquer
The sub arrays are already considered sorted.

Step 3: Merge (Combine)
• Now, merge [1] and [7] to get [1, 7].
• Merge [2], and [4] to get [2, 4].
• Merge [6] and [5] to get [5, 6].
• Merge [1, 7] and [2, 4] to get [1, 2, 4, 7].
• Merge [1, 2, 4, 7] and [5, 6] to get [1, 2, 4, 5, 6, 7].
The most crucial yet confusing step in the merge sort algorithm is the merging process. Two sub-arrays are combined while comparing the smallest element of each array and sorting them. This process continues unless all the sub-arrays have not been merged.

Implementing Merge Sort in C#

Let’s see how the Merge Sort algorithm works programmatically.

using System;
using System.Collections.Generic;
class Sorting {
  public static void MergeSort(int[] numbers)  //Calling the method recursively
  {
      MergeSort(numbers, 0, numbers.Length - 1);
  }
  private static void MergeSort(int[] numbers, int left, int right)  //Overloaded merge sort
  {
      if (left < right) //Checking if the left is less than right
    {
        int middle = left + (right - left) / 2;  //Find the middle point

        MergeSort(numbers, left, middle);  //Sorting the first halves recursively 
        MergeSort(numbers, middle + 1, right);

        Merge(numbers, left, middle, right);  //Merging the sorted halves
    }
  }
  
  private static void Merge(int[] num, int left, int middle, int right)  //Merging the sorted sub arrays
{
    int number1 = middle - left + 1;
    int number2 = right - middle;

    int[] leftArray = new int[number1];  //Temporary arrays
    int[] rightArray = new int[number2];

    Array.Copy(num, left, leftArray, 0, number1);  //Storing data in temporary arrays
    Array.Copy(num, middle + 1, rightArray, 0, number2);

    // Initialize the initial indexes of the two sub-arrays and the merged array
    int i = 0, j = 0, k = left;

    // Merging the temporary arrays
    while (i < number1 && j < number2)
    {
        if (leftArray[i] <= rightArray[j])
        {
            num[k] = leftArray[i];
            i++;
        }
        else
        {
            num[k] = rightArray[j];
            j++;
        }
        k++;
    }

    // Copy any remaining elements of leftArray
    while (i < number1)
    {
        num[k] = leftArray[i];
        i++;
        k++;
    }

    // Copy any remaining elements of rightArray
    while (j < number2)
    {
        num[k] = rightArray[j];
        j++;
        k++;
    }
}
static void Main() {
    int[] nums = {2, 4, 1, 6, 5, 7};
    MergeSort(nums);
    for(int i=0; i<nums.Length; i++)
    {
        Console.Write(nums[i] + " ");
    }
  }
}

Advantages of Merge Sort Algorithm

• The merge sort provides a consistent performance making it an ideal choice for the time-sensitive applications.
• Merge sort is a stable sorting algorithm as it preserves the relative order of the elements. It is ideal in the scenarios where the original order of the elements must be maintained.
• It is highly useful for external sorting where the data to be sorted is too large to be stored in the memory.

Conclusively, the merge sort algorithm provides a robust and efficient sorting solution for smaller as well as large data sets. Although it requires extra space for merging process, it is a phenomenal algorithm in data structures and algorithms due to its stability, consistency and external sorting capabilities. Therefore, understanding Merge sort algorithm is the most important for the beginners. In the next article, we will learn about the Quick Sort algorithm.