Skip to content

Instantly share code, notes, and snippets.

@vector623
Last active January 6, 2025 02:55
Show Gist options
  • Save vector623/3d8e069c550bf5711a6912de2d29f3c6 to your computer and use it in GitHub Desktop.
Save vector623/3d8e069c550bf5711a6912de2d29f3c6 to your computer and use it in GitHub Desktop.
C# Functional MergeSort
public class Functional
{
public int[] MergeSort(int[] array)
{
if (array.Length < 2)
return array;
var (arrayA, arrayB) = Split(array);
var sortedA = MergeSort(arrayA);
var sortedB = MergeSort(arrayB);
var mergedArray = Merge(sortedA, sortedB);
return mergedArray;
}
private (int[] arrayA, int[] arrayB) Split(int[] array)
{
var arrayA = array
.Take(array.Length / 2)
.ToArray();
var arrayB = array
.Skip(array.Length / 2)
.ToArray();
return (arrayA, arrayB);
}
private int[] Merge(int[] sortedA, int[] sortedB)
{
return Enumerable.Range(0, sortedA.Length + sortedB.Length)
.Aggregate(
seed: new
{
arrayA = sortedA as IEnumerable<int>,
arrayB = sortedB as IEnumerable<int>,
merged = new List<int>() as IEnumerable<int>,
},
(aggr, _) => (aggr.arrayA, aggr.arrayB) switch
{
var (arrayA, arrayB) when (arrayA.Any() && !arrayB.Any()) ||
(arrayA.Any() && arrayB.Any() && arrayA.First() <= arrayB.First())
=> new
{
arrayA = aggr.arrayA.Skip(1),
aggr.arrayB,
merged = aggr.merged.Append(arrayA.First()),
},
var (arrayA, arrayB) when (!arrayA.Any() && arrayB.Any()) ||
(arrayA.Any() && arrayB.Any() && arrayA.First() > arrayB.First())
=> new
{
aggr.arrayA,
arrayB = aggr.arrayB.Skip(1),
merged = aggr.merged.Append(arrayB.First()),
},
})
.merged
.ToArray();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment