Merge sort in C#
Sort an array by divide and conquer. Sort each half, then merge the two sorted halves into one sorted array.
- File
MergeSort.cs, 46 lines- Level
- Toolchain
- .NET 10, C# 14, xUnit
- Test framework
- xUnit
- Run the tests
dotnet test
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
namespace Algorithm;
/// <summary>Merge sort.</summary>
public static class MergeSort
{
/// <summary>Sorts a in place, in non-decreasing order. The sort is stable.</summary>
public static void Sort<T>(Span<T> a) where T : IComparable<T>
{
var b = new T[(a.Length + 1) / 2];
Sort(a, b);
}
private static void Sort<T>(Span<T> a, T[] b) where T : IComparable<T>
{
if (a.Length <= 1) return; // @line L1
int mid = a.Length / 2; // @line L2
Sort(a[..mid], b); // @line L3
Sort(a[mid..], b); // @line L4
Merge(a, mid, b); // @line L5
}
private static void Merge<T>(Span<T> a, int mid, T[] b) where T : IComparable<T>
{
a[..mid].CopyTo(b); // @line L6
int i = 0, j = mid, k = 0; // @line L7
while (i < mid && j < a.Length) // @line L8
{
if (b[i].CompareTo(a[j]) <= 0) // @line L9
{
a[k] = b[i++];
}
else
{
a[k] = a[j++]; // @line L10
}
k++; // @line L11
}
while (i < mid) // @line L12
{
a[k++] = b[i++]; // @line L13
}
}
}
MergeSortTests.cs 43 lines
// SPDX-License-Identifier: MIT
// Part of https://algorithm.tamnd.com/merge-sort/. The authors are listed in prov/4MRG7S.jsonl.
using Algorithm;
using Xunit;
public class MergeSortTests
{
[Fact]
public void Example()
{
long[] a = [38, 27, 43, 3, 9, 82, 10];
MergeSort.Sort<long>(a);
Assert.Equal(new long[] { 3, 9, 10, 27, 38, 43, 82 }, a);
}
[Fact]
public void Edges()
{
foreach (var a in new[] { new long[] { }, new long[] { 1 }, new long[] { 2, 1 }, new long[] { 1, 1, 1 }, new long[] { 3, 2, 1 } })
{
var want = (long[])a.Clone();
Array.Sort(want);
MergeSort.Sort<long>(a);
Assert.Equal(want, a);
}
}
[Fact]
public void RandomAgainstArraySort()
{
var rng = new Random(2150);
for (int t = 0; t < 500; t++)
{
var a = new long[rng.Next(61)];
for (int i = 0; i < a.Length; i++) a[i] = rng.Next(101) - 50;
var want = (long[])a.Clone();
Array.Sort(want);
MergeSort.Sort<long>(a);
Assert.Equal(want, a);
}
}
}
What the next level needs
- the native tests did not run in this build
- I1 needs the shared cases of the contract and the JSON adapter (09.2), which are M0 work