Sorting is a fundamental part of programming, and Merge Sort is one of the most efficient algorithms for handling large datasets. Unlike simple algorithms like Insertion or Bubble Sort, Merge Sort uses a divide-and-conquer approach. It splits the array into smaller subarrays, sorts each subarray, and then merges them back together into a single sorted array. This makes it very powerful, especially when working with large or complex datasets.
with hands-on learning.
get the skills and confidence to land your next move.
Merge Sort is widely used in real-world applications where efficiency matters, such as database systems, search engines, and data analysis tools. Learning Merge Sort in C# is an excellent opportunity for beginners to understand recursion, array manipulation, and efficient algorithm design. With predefined data examples, beginners can clearly see how the array is divided and merged step by step, which makes the learning process much easier and engaging.
Program 1: Merge Sort Using Recursion (Ascending Order)
This program demonstrates the standard recursive Merge Sort algorithm, sorting a predefined array in ascending order.
using System;
class Program
{
static void Merge(int[] arr, int left, int mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
Array.Copy(arr, left, L, 0, n1);
Array.Copy(arr, mid + 1, R, 0, n2);
int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
static void MergeSort(int[] arr, int left, int right)
{
if (left < right)
{
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
static void Main()
{
int[] arr = { 12, 11, 13, 5, 6, 7 };
MergeSort(arr, 0, arr.Length - 1);
Console.WriteLine("Sorted array in ascending order:");
foreach (int num in arr)
Console.Write(num + " ");
Console.WriteLine();
}
}In this program, the array is split into halves repeatedly, and each half is sorted recursively. The Merge function then combines the halves into a sorted sequence. Beginners can visualize how smaller arrays are handled first, making it easier to understand recursion.
Program 2: Merge Sort in Descending Order
By changing the comparison in the merge step, Merge Sort can sort arrays in descending order.
using System;
class Program
{
static void Merge(int[] arr, int left, int mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
Array.Copy(arr, left, L, 0, n1);
Array.Copy(arr, mid + 1, R, 0, n2);
int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
{
if (L[i] >= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
static void MergeSort(int[] arr, int left, int right)
{
if (left < right)
{
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
static void Main()
{
int[] arr = { 12, 11, 13, 5, 6, 7 };
MergeSort(arr, 0, arr.Length - 1);
Console.WriteLine("Sorted array in descending order:");
foreach (int num in arr)
Console.Write(num + " ");
Console.WriteLine();
}
}This program shows that by modifying just one condition, you can reverse the sort order. Beginners can see the flexibility of Merge Sort for different use cases.
Program 3: Merge Sort With Strings
Merge Sort can also handle string arrays, sorting them alphabetically.
using System;
class Program
{
static void Merge(string[] arr, int left, int mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
string[] L = new string[n1];
string[] R = new string[n2];
Array.Copy(arr, left, L, 0, n1);
Array.Copy(arr, mid + 1, R, 0, n2);
int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
{
if (string.Compare(L[i], R[j]) <= 0)
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
static void MergeSort(string[] arr, int left, int right)
{
if (left < right)
{
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
static void Main()
{
string[] arr = { "Orange", "Apple", "Banana", "Mango" };
MergeSort(arr, 0, arr.Length - 1);
Console.WriteLine("Sorted string array:");
foreach (string str in arr)
Console.Write(str + " ");
Console.WriteLine();
}
}This example shows that Merge Sort is not limited to numbers. Beginners can use it to sort names, words, or any data that can be compared.
Program 4: Merge Sort With Floating-Point Numbers
Merge Sort can handle decimal numbers, making it versatile for financial or scientific applications.
using System;
class Program
{
static void Merge(double[] arr, int left, int mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
double[] L = new double[n1];
double[] R = new double[n2];
Array.Copy(arr, left, L, 0, n1);
Array.Copy(arr, mid + 1, R, 0, n2);
int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
{
if (L[i] <= R[j])
{
arr[k] = L[i];
i++;
}
else
{
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1)
{
arr[k] = L[i];
i++;
k++;
}
while (j < n2)
{
arr[k] = R[j];
j++;
k++;
}
}
static void MergeSort(double[] arr, int left, int right)
{
if (left < right)
{
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
}
}
static void Main()
{
double[] arr = { 12.5, 3.7, 7.9, 1.2, 9.8 };
MergeSort(arr, 0, arr.Length - 1);
Console.WriteLine("Sorted double array:");
foreach (double num in arr)
Console.Write(num + " ");
Console.WriteLine();
}
}This shows Merge Sort’s flexibility with different numeric types, which is very useful in scientific computing or financial calculations.
Frequently Asked Questions (FAQ)
Q1: What is Merge Sort?
Merge Sort is a divide-and-conquer sorting algorithm that splits arrays into smaller pieces, sorts them, and merges them back together in order.
Q2: Why is Merge Sort efficient?
It has a time complexity of O(n log n), which is faster than simple algorithms like Bubble Sort or Insertion Sort for large datasets.
Q3: Can Merge Sort be used on strings or decimals?
Yes. As long as elements can be compared, Merge Sort can sort numbers, strings, or floating-point values.
Q4: Is Merge Sort recursive or iterative?
It is usually implemented recursively, but an iterative version also exists. The recursive version is easier for beginners to understand.
Q5: When should I avoid Merge Sort?
Merge Sort requires extra memory for temporary arrays, so it might not be ideal for systems with very limited memory.
Conclusion
Merge Sort is a powerful and versatile algorithm in C# that teaches beginners important programming concepts like recursion, array manipulation, and efficient sorting. By experimenting with integers, decimals, and strings, beginners can gain confidence in implementing complex algorithms. Practicing Merge Sort with predefined data helps learners visualize each step, making it easier to progress to advanced sorting techniques such as Quick Sort or Heap Sort. Understanding Merge Sort is an essential step toward becoming a confident and skilled C# programmer.
