C# Merge Sort
last modified March 8, 2025
This article explores the Merge Sort algorithm in C#, demonstrating its use for sorting numeric and textual data in ascending and descending order, with a benchmark against Quick Sort.
An algorithm is a structured sequence of steps crafted to solve a problem or perform a task efficiently. It's a cornerstone of programming, driving computational solutions.
Sorting means organizing data into a specific sequence, such as ascending or descending. It's vital for enhancing data retrieval and analysis in various applications.
Common Sorting Algorithms
Here are some well-known sorting algorithms:
- Bubble Sort
- Selection Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- Heap Sort
Merge Sort Algorithm
Merge Sort is a divide-and-conquer algorithm that splits an array into two halves, recursively sorts each half, and then merges them back together in sorted order.
With a consistent time complexity of O(n log n), Merge Sort is stable and efficient, though it requires extra space for merging. It excels with linked lists and large datasets.
Merge Sort Example
Below is a C# implementation of Merge Sort for numbers and strings using top-level statements.
// MergeSort.cs
int[] MergeSort(int[] arr)
{
if (arr.Length <= 1)
{
return arr;
}
int mid = arr.Length / 2;
int[] left = MergeSort(arr[..mid]);
int[] right = MergeSort(arr[mid..]);
return Merge(left, right);
}
int[] Merge(int[] left, int[] right)
{
var result = new List<int>(left.Length + right.Length);
int i = 0, j = 0;
for (; i < left.Length && j < right.Length;)
{
if (left[i] < right[j])
{
result.Add(left[i]);
i++;
}
else
{
result.Add(right[j]);
j++;
}
}
result.AddRange(left[i..]);
result.AddRange(right[j..]);
return result.ToArray();
}
string[] MergeSortStrings(string[] arr)
{
if (arr.Length <= 1)
{
return arr;
}
int mid = arr.Length / 2;
string[] left = MergeSortStrings(arr[..mid]);
string[] right = MergeSortStrings(arr[mid..]);
return MergeStrings(left, right);
}
string[] MergeStrings(string[] left, string[] right)
{
var result = new List<string>(left.Length + right.Length);
int i = 0, j = 0;
for (; i < left.Length && j < right.Length;)
{
if (string.Compare(left[i], right[j]) < 0)
{
result.Add(left[i]);
i++;
}
else
{
result.Add(right[j]);
j++;
}
}
result.AddRange(left[i..]);
result.AddRange(right[j..]);
return result.ToArray();
}
int[] SortDescending(int[] arr)
{
int[] sorted = MergeSort(arr);
for (int i = 0, j = sorted.Length - 1; i < j; i++, j--)
{
(sorted[i], sorted[j]) = (sorted[j], sorted[i]);
}
return sorted;
}
string[] SortStringsDescending(string[] arr)
{
string[] sorted = MergeSortStrings(arr);
for (int i = 0, j = sorted.Length - 1; i < j; i++, j--)
{
(sorted[i], sorted[j]) = (sorted[j], sorted[i]);
}
return sorted;
}
int[] numbers = [38, 27, 43, 3, 9, 82, 10];
string[] words = ["apple", "banana", "cherry", "date", "elderberry"];
Console.WriteLine("Sorted numbers (ascending): " + string.Join(" ", MergeSort(numbers)));
Console.WriteLine("Sorted numbers (descending): " + string.Join(" ", SortDescending(numbers)));
Console.WriteLine("Sorted words (ascending): " + string.Join(" ", MergeSortStrings(words)));
Console.WriteLine("Sorted words (descending): " + string.Join(" ", SortStringsDescending(words)));
The MergeSort method recursively splits and
merges integer arrays, while MergeSortStrings
does the same for strings. The Merge helper
combines sorted halves.
For descending order, SortDescending and
SortStringsDescending reverse the ascending
result. This approach leverages C#'s array operations for
clarity and efficiency.
Comparing Merge Sort with Quick Sort
Merge Sort guarantees O(n log n) time complexity and stability, making it reliable. Quick Sort averages O(n log n) but can degrade to O(n²) in worst-case scenarios, like sorted data.
This benchmark compares their performance on a large dataset in C#.
// Benchmark.cs
using System.Diagnostics;
int[] MergeSort(int[] arr)
{
if (arr.Length <= 1)
{
return arr;
}
int mid = arr.Length / 2;
int[] left = MergeSort(arr[..mid]);
int[] right = MergeSort(arr[mid..]);
return Merge(left, right);
}
int[] Merge(int[] left, int[] right)
{
var result = new List<int>(left.Length + right.Length);
int i = 0, j = 0;
for (; i < left.Length && j < right.Length;)
{
if (left[i] < right[j])
{
result.Add(left[i]);
i++;
}
else
{
result.Add(right[j]);
j++;
}
}
result.AddRange(left[i..]);
result.AddRange(right[j..]);
return result.ToArray();
}
int[] QuickSort(int[] arr)
{
if (arr.Length <= 1)
{
return arr;
}
int pivot = arr[arr.Length / 2];
var left = new List<int>();
var middle = new List<int>();
var right = new List<int>();
foreach (int x in arr)
{
if (x < pivot)
{
left.Add(x);
}
else if (x == pivot)
{
middle.Add(x);
}
else
{
right.Add(x);
}
}
return [.. QuickSort(left.ToArray()), .. middle, .. QuickSort(right.ToArray())];
}
Random rand = new(Random.Shared.Next());
int[] numbers = new int[10000];
for (int i = 0; i < numbers.Length; i++)
{
numbers[i] = rand.Next(10000);
}
int[] mergeData = numbers.ToArray();
Stopwatch sw = Stopwatch.StartNew();
MergeSort(mergeData);
double mergeTime = sw.Elapsed.TotalSeconds;
int[] quickData = numbers.ToArray();
sw = Stopwatch.StartNew();
QuickSort(quickData);
double quickTime = sw.Elapsed.TotalSeconds;
Console.WriteLine($"Merge Sort Time: {mergeTime:F6} seconds");
Console.WriteLine($"Quick Sort Time: {quickTime:F6} seconds");
This benchmark tests Merge Sort and Quick Sort on 10,000 random integers. Merge Sort creates new arrays during merging, while Quick Sort partitions in a similar recursive manner.
Merge Sort's predictable performance contrasts with Quick Sort's potential speed advantage due to better cache locality. Actual results vary, but Merge Sort ensures consistency.
Source
This tutorial explained Merge Sort in C#, with examples for numbers and text, and a benchmark against Quick Sort.
Author
List all C# tutorials.