Program.cs

using System;

class MainClass
{
	private static int[] copyArray(int[] A, int start, int end)
	{

		int[] result = new int[end - start];

		int cnt = 0;
		for (int i = start; i < end; i++)
		{
			result[cnt] = A[i];
			cnt++;
		}

		return result;
	}


	public static int[] Sort(int[] data)
	{

		if (data.Length <= 1)
			return data;

		var length = data.Length / 2;

		int[] LeftArray = copyArray(data, 0, length);
		int[] RightArray = copyArray(data, length, data.Length);

		RightArray = Sort(RightArray);
		LeftArray = Sort(LeftArray);

		return merge(RightArray, LeftArray);
	}

	public static int[] merge(int[] right, int[] left)
	{


		int[] merged = new int[right.Length + left.Length];

		int cntright = 0;
		int cntleft = 0;

		for (int i = 0; i < merged.Length; i++)
		{
			if (cntright == right.Length)
			{
				merged[i] = left[cntleft];
				cntleft++;
			}
			else if (cntleft == left.Length)
			{
				merged[i] = right[cntright];
				cntright++;
			}
			else if (right[cntright] <= left[cntleft])
			{
				merged[i] = right[cntright];
				cntright++;
			}
			else
			{
				merged[i] = left[cntleft];
				cntleft++;
			}
		}

		return merged;
	}




	public static void Main(string[] args)
	{
		long seed = DateTime.Now.Ticks;
		Random random = new Random((int) seed);
		Console.WriteLine("Seed = " + seed);
		int[] array1 = createRandomIntArray(2000 * 1000, random);
		int[] array2 = (int[]) array1.Clone();

		long start = getMilliseconds();
		array1 = Sort(array1);
		long end = getMilliseconds();

		Console.WriteLine("OP mergesort in {0} milliseconds.", end - start);

		start = getMilliseconds();
		coderoddeMergesort(array2);
		end = getMilliseconds();


		Console.WriteLine("coderodde mergesort in {0} milliseconds.", end - start);
		Console.WriteLine("Algorithms agree: {0}.", intArrayEquals(array1, array2));
	}

	private static long getMilliseconds()
	{
		return DateTime.Now.Ticks / TimeSpan.TicksPerMillisecond;
	}

	private static int[] createRandomIntArray(int size, Random random)
	{
		int[] array = new int[size];

		for (int i = 0; i < size; ++i)
		{
			array[i] = random.Next();
		}

		return array;
	}

	public static void coderoddeMergesort(int[] array)
	{
		coderoddeMergesort(array, 0, array.Length);
	}

	public static void coderoddeMergesort(int[] array, int index, int length)
	{
		// Do the sanity checks for input. I am not a C# programmer so don't know.
		int[] aux = new int[length];
		Array.Copy(array, index, aux, 0, length);
		coderoddeMergesort(aux, array, 0, index, length);
	}

	private static void coderoddeMergesort(int[] source,
										   int[] target,
										   int sourceOffset,
										   int targetOffset,
										   int rangeLength)
	{
		if (rangeLength < 2)
		{
			return;
		}

		int middle = rangeLength / 2;

		coderoddeMergesort(target,
						   source,
						   targetOffset,
						   sourceOffset,
						   middle);

		coderoddeMergesort(target,
						   source,
						   targetOffset + middle,
						   sourceOffset + middle,
						   rangeLength - middle);

		coderoddeMerge(source,
					   target,
					   sourceOffset,
					   targetOffset,
					   middle,
					   rangeLength - middle);
	}

	private static void coderoddeMerge(int[] source,
									   int[] target,
									   int sourceOffset,
									   int targetOffset,
									   int leftRunLength,
									   int rightRunLength)
	{
		int targetIndex = targetOffset;
		int leftIndex = sourceOffset;
		int leftIndexBound = leftIndex + leftRunLength;
		int rightIndex = leftIndexBound;
		int rightIndexBound = rightIndex + rightRunLength;

		while (leftIndex != leftIndexBound && rightIndex != rightIndexBound)
		{
			target[targetIndex++] =
				source[rightIndex] < source[leftIndex] ?
				source[rightIndex++] :
				source[leftIndex++];
		}

		Array.Copy(source, leftIndex, target, targetIndex, leftIndexBound - leftIndex);
		Array.Copy(source, rightIndex, target, targetIndex, rightIndexBound - rightIndex);
	}

	private static bool intArrayEquals(int[] array1, int[] array2)
	{
		if (array1.Length != array2.Length)
		{
			return false;
		}

		for (int i = 0; i < array1.Length; ++i)
		{
			if (array1[i] != array2[i])
			{
				return false;
			}
		}

		return true;
	}
}