Created
July 22, 2015 15:15
-
-
Save stanroze/11c229051218093eea6e to your computer and use it in GitHub Desktop.
Converting my integer array mergesort to a generic merge sort extension
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
public static class Ext | |
{ | |
private class ComparableToComparer<T> : Comparer<T> where T : IComparable<T> | |
{ | |
public override int Compare(T x, T y) | |
{ | |
return x.CompareTo(y); | |
} | |
} | |
public static IList<T> MergeSort<T>(this IList<T> arr) where T : IComparable<T> | |
{ | |
return arr.MergeSort(new ComparableToComparer<T>()); | |
} | |
public static IList<T> MergeSort<T>(this IList<T> arr, IComparer<T> comparer ) | |
{ | |
if (arr.Count == 1) | |
return arr; | |
//get a half point | |
int mid = arr.Count / 2; | |
T[] left = new T[mid]; | |
T[] right = new T[arr.Count - mid]; //reason for length - mid is due to halfpoint of an odd length array | |
//fill up left - to the half point from original | |
for (int i = 0; i < mid; i++) | |
{ | |
left[i] = arr[i]; | |
} | |
//fill up right - need j because right arr starts at 0, start at mid for the parent array | |
for (int i = mid, j = 0; i < arr.Count; i++, j++) | |
{ | |
right[j] = arr[i]; | |
} | |
//you have 2 arrays, so sort both of them | |
//you can of course use merge to return a new array | |
//but its better to sort the array in space | |
var sortedLeft = left.MergeSort(comparer); | |
var sortedRight = right.MergeSort(comparer); | |
Merge(sortedLeft, sortedRight, arr ,comparer); | |
return arr; | |
} | |
private static void Merge<T>(IList<T> arrA, IList<T> arrB, IList<T> aux, IComparer<T> comparer ) | |
{ | |
//you can of course return a "new" array here, but why allocate more | |
int aindex = 0; | |
int bindex = 0; | |
int auxindex = 0; | |
//we need to compare each element in both arrays and only pick the smallest one | |
//once the smallest one is picked, increment in indexer in the array it was picked from | |
//and leave the other indexer untouched. | |
//always increment the auxilary index | |
while (aindex < arrA.Count && bindex < arrB.Count) | |
{ | |
if (comparer.Compare(arrA[aindex], arrB[bindex]) < 0) | |
{ | |
aux[auxindex] = arrA[aindex]; | |
aindex++; | |
} | |
else if (comparer.Compare(arrB[bindex], arrA[aindex]) < 0) | |
{ | |
aux[auxindex] = arrB[bindex]; | |
bindex++; | |
} | |
else | |
{ | |
aux[auxindex] = arrA[aindex]; | |
aindex++; | |
} | |
auxindex++; | |
} | |
//in the even that all the smallest numbers were in one of the arrays instead of other | |
//we need to fill up the parent array with the items from the other side, so just | |
//fill up until we cant anymore | |
//first do from A Array | |
while (aindex < arrA.Count) | |
{ | |
aux[auxindex] = arrA[aindex]; | |
aindex++; | |
auxindex++; | |
} | |
//then do the same from B array | |
while (bindex < arrB.Count) | |
{ | |
aux[auxindex] = arrB[bindex]; | |
bindex++; | |
auxindex++; | |
} | |
//done :D | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment