Last active
January 27, 2021 21:19
-
-
Save Swimburger/527fadc158da41ca3f681992190ab9ff to your computer and use it in GitHub Desktop.
Generic Merge Sort in C#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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