Arguably the trickier part of the Merge Sort is to implement the merge itself. The pseudo code for it when taken from the aforementioned link and rendered in genericized C# looks as follows:

public static T[] Merge<T>(T[] left, T[] right) where T : IComparable<T>
{
List<T> result = new List<T>();
int leftIndex = 0;
int rightIndex = 0;
while (left.Length - leftIndex > 0 || right.Length - rightIndex > 0)
{
if (left.Length - leftIndex > 0 && right.Length - rightIndex > 0)
{
if (left[leftIndex].CompareTo(right[rightIndex]) < 1)
{
result.Add(left[leftIndex]);
leftIndex++;
}
else
{
result.Add(right[rightIndex]);
rightIndex++;
}
}
else if (left.Length - leftIndex > 0)
{
result.Add(left[leftIndex]);
leftIndex++;
}
else
{
result.Add(right[rightIndex]);
rightIndex++;
}
}
return result.ToArray();
}

### Like this:

Like Loading...