MergeSorter.cs

usingSystem.Collections.Generic;
usingAlgorithms.Common;

namespaceAlgorithms.Sorting
{
publicstaticclassMergeSorter
{
//
// Public merge-sort API
publicstaticList<T>MergeSort<T>(thisList<T>collection,Comparer<T>comparer=null)
{
comparer=comparer??Comparer<T>.Default;

returnInternalMergeSort(collection,comparer);
}


//
// Private static method
// Implements the recursive merge-sort algorithm
privatestaticList<T>InternalMergeSort<T>(List<T>collection,Comparer<T>comparer)
{
if(collection.Count<2)
{
returncollection;
}

intmidIndex=collection.Count/2;

varleftCollection=collection.GetRange(0,midIndex);
varrightCollection=collection.GetRange(midIndex,collection.Count-midIndex);

leftCollection=InternalMergeSort<T>(leftCollection,comparer);
rightCollection=InternalMergeSort<T>(rightCollection,comparer);

returnInternalMerge<T>(leftCollection,rightCollection,comparer);
}


//
// Private static method
// Implements the merge function inside the merge-sort
privatestaticList<T>InternalMerge<T>(List<T>leftCollection,List<T>rightCollection,Comparer<T>comparer)
{
intleft=0;
intright=0;
intindex;
intlength=leftCollection.Count+rightCollection.Count;

List<T>result=newList<T>(length);

for(index=0;right<rightCollection.Count&&left<leftCollection.Count;++index)
{
if(comparer.Compare(rightCollection[right],leftCollection[left])<=0)// rightElement <= leftElement
{
//resultArray.Add(rightCollection[right]);
result.Insert(index,rightCollection[right++]);
}
else
{
//result.Add(leftCollection[left]);
result.Insert(index,leftCollection[left++]);
}
}

//
// At most one of left and right might still have elements left

while(right<rightCollection.Count)
{
result.Insert(index++,rightCollection[right++]);
}

while(left<leftCollection.Count)
{
result.Insert(index++,leftCollection[left++]);
}

returnresult;
}
}
}