Skip to content

Instantly share code, notes, and snippets.

@Swimburger
Last active January 27, 2021 21:19
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Swimburger/527fadc158da41ca3f681992190ab9ff to your computer and use it in GitHub Desktop.
Save Swimburger/527fadc158da41ca3f681992190ab9ff to your computer and use it in GitHub Desktop.
Generic Merge Sort in C#
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
static void Main(string[] args)
{
var randomNumbers = new int[] { 5, 4, 5, 7, 6, 9, 4, 1, 1, 3, 4, 50, 56, 41 };
var sortedNumbers = MergeSort(randomNumbers.AsEnumerable());
Console.WriteLine("Merge Sort:");
PrintList(sortedNumbers);
Console.ReadKey();
Console.Clear();
}
private static IEnumerable<T> MergeSort<T>(IEnumerable<T> list) where T : IComparable
{
T[] items = list.ToArray();
return InternalMergeSort(items);
}
private static T[] InternalMergeSort<T>(T[] items) where T : IComparable
{
int listLength = items.Length;
if (listLength == 1)
{
return items;
}
int median = listLength / 2;
T[] left = new T[median];
T[] right = new T[listLength - median];
Array.Copy(items, left, left.Length);
Array.Copy(items, median, right, 0, right.Length);
InternalMergeSort(left);
InternalMergeSort(right);
return Merge(items, left, right);
}
private static T[] Merge<T>(T[] items, T[] left, T[] right) where T : IComparable
{
int leftIndex = 0;
int rightIndex = 0;
int leftLength = left.Length;
int rightLength = right.Length;
int totalItems = leftLength + rightLength;
for (int targetIndex = 0; targetIndex < totalItems; targetIndex++)
{
if(leftIndex >= leftLength)
{
items[targetIndex] = right[rightIndex];
rightIndex++;
}
else if(rightIndex >= right.Length)
{
items[targetIndex] = left[leftIndex];
leftIndex++;
}
else if(left[leftIndex].CompareTo(right[rightIndex]) < 0)
{
items[targetIndex] = left[leftIndex];
leftIndex++;
}
else
{
items[targetIndex] = right[rightIndex];
rightIndex++;
}
}
return items;
}
private static void PrintList<T>(IEnumerable<T> list)
{
foreach (var item in list)
{
Console.WriteLine(item);
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment