Skip to content

Instantly share code, notes, and snippets.

@stanroze
Created July 22, 2015 15:15
Show Gist options
  • Save stanroze/11c229051218093eea6e to your computer and use it in GitHub Desktop.
Save stanroze/11c229051218093eea6e to your computer and use it in GitHub Desktop.
Converting my integer array mergesort to a generic merge sort extension
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