Skip to content

Instantly share code, notes, and snippets.

@vector623
Last active January 6, 2025 02:48
Show Gist options
  • Save vector623/f817a17e8dbecbe974361af99bdad4c2 to your computer and use it in GitHub Desktop.
Save vector623/f817a17e8dbecbe974361af99bdad4c2 to your computer and use it in GitHub Desktop.
C# Imperative MergeSort
public class Imperative
{
public int[] MergeSort(int[] array)
{
if (array.Length <= 1) return array;
var (arrayA, arrayB) = Split(array);
var sortedA = MergeSort(arrayA);
var sortedB = MergeSort(arrayB);
var mergedArray = Merge(sortedA, sortedB);
return mergedArray;
}
public (int[], int[]) Split(int[] array)
{
var arrayA = new int[array.Length / 2];
Array.Copy(array, 0, arrayA, 0, arrayA.Length);
var arrayB = new int[array.Length - arrayA.Length];
Array.Copy(array, arrayA.Length, arrayB, 0, arrayB.Length);
return (arrayA, arrayB);
}
private int[] Merge(int[] arrayA, int[] arrayB)
{
var merged = new int[arrayA.Length + arrayB.Length];
(int a, int b) = (0, 0);
while (a < arrayA.Length && b < arrayB.Length)
{
if (arrayA[a] < arrayB[b])
{
merged[a + b] = arrayA[a];
a++;
}
else
{
merged[a + b] = arrayB[b];
b++;
}
}
for (int i = a; i < arrayA.Length; i++)
{
merged[i + b] = arrayA[i];
}
for (int i = b; i < arrayB.Length; i++)
{
merged[a + i] = arrayB[i];
}
return merged;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment