Data Structures in C# - Exploring Merge Sort

Screenshot from the tutorial

Understanding Merge Sort in C#: A Comprehensive Guide

Sorting algorithms are a fundamental aspect of data structures and programming. Among these, Merge Sort is a popular choice due to its efficiency and systematic approach. In this blog post, we will explore the Merge Sort algorithm specifically in C#, drawing from the insights of the YouTube video "Data Structures in C# - Exploring Merge Sort."

What is Merge Sort?

Merge Sort is a divide-and-conquer algorithm that sorts an array by recursively dividing it into two halves, sorting each half, and then merging the sorted halves back together. This method ensures a consistent O(n log n) time complexity, making it efficient for larger datasets.

Key Characteristics of Merge Sort:

• Stable: It maintains the relative order of equal elements.
• Not In-Place: It requires additional space proportional to the array size.
• Divide and Conquer: It recursively breaks down the problem, making it easier to solve.

How Merge Sort Works

The Merge Sort algorithm follows these steps:

1. Divide: Split the array into two halves until each subarray contains a single element.
2. Conquer: Recursively sort the two halves.
3. Combine: Merge the two sorted halves into a single sorted array.

Visual Representation

For a better understanding, consider the following example of an unsorted array:

[38, 27, 43, 3, 9, 82, 10]

1. Divide:

   [38, 27, 43] and [3, 9, 82, 10]
   

2. Further Divide:

   [38] [27, 43] and [3, 9] [82, 10]
   

3. Continue until Base Case:

   [38] [27] [43] and [3] [9] [82] [10]
   

4. Merge:

   [27, 38, 43] and [3, 9, 10, 82]
   

5. Final Merge:

   [3, 9, 10, 27, 38, 43, 82]
   

Implementing Merge Sort in C#

Let’s dive into a practical implementation of Merge Sort in C#. Below is the code that demonstrates this algorithm:

using System;

class MergeSortExample
{
    static void Main(string[] args)
    {
        int[] array = { 38, 27, 43, 3, 9, 82, 10 };
        Console.WriteLine("Unsorted array:");
        PrintArray(array);

        MergeSort(array, 0, array.Length - 1);

        Console.WriteLine("\nSorted array:");
        PrintArray(array);
    }

    static void MergeSort(int[] array, int left, int right)
    {
        if (left < right)
        {
            int mid = (left + right) / 2;

            // Recursively sort the two halves
            MergeSort(array, left, mid);
            MergeSort(array, mid + 1, right);

            // Merge the sorted halves
            Merge(array, left, mid, right);
        }
    }

    static void Merge(int[] array, int left, int mid, int right)
    {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        Array.Copy(array, left, leftArray, 0, n1);
        Array.Copy(array, mid + 1, rightArray, 0, n2);

        int i = 0, j = 0, k = left;

        while (i < n1 && j < n2)
        {
            if (leftArray[i] <= rightArray[j])
            {
                array[k++] = leftArray[i++];
            }
            else
            {
                array[k++] = rightArray[j++];
            }
        }

        while (i < n1)
        {
            array[k++] = leftArray[i++];
        }

        while (j < n2)
        {
            array[k++] = rightArray[j++];
        }
    }

    static void PrintArray(int[] array)
    {
        foreach (var item in array)
        {
            Console.Write(item + " ");
        }
        Console.WriteLine();
    }
}

Explanation of the Code

• Main Method: Initializes an array and calls the MergeSort method.
• MergeSort Method: Recursively splits the array until the base case is reached, where the array has one or zero elements.
• Merge Method: Combines the two sorted halves into a single sorted array.
• PrintArray Method: Utility to print the array before and after sorting.

Conclusion

Merge Sort is an essential sorting algorithm that demonstrates the power of divide-and-conquer strategies. Its efficiency makes it suitable for various applications, especially when dealing with large datasets. By implementing it in C#, you not only enhance your programming skills but also gain a deeper understanding of data structures.

For further exploration, consider testing the algorithm with different datasets or integrating it into larger applications. Happy coding!

Another view from the tutorial

---

Connect with SkillBakery Studios

Explore more tutorials, tools, and resources:

• skillbakery.com
• Facebook
• X (Twitter)
• YouTube Channel

Posted by SkillBakery Studios