Merge Sort

namespace MergeSort
{
    using System;

    public class MergeSortArray
    {
        public static void Main(string[] args)
        {
            int[] array = { 5, 9, 2, 3, 6 };

            MergeSort(array, 0, array.Length - 1);

            Console.WriteLine("Sorted (Merge Sort):");
            Console.WriteLine("[{0}]", string.Join(", ", array));
        }

        private static void MergeSort(int[] array, int start, int end)
        {
            if (start < end)
            {
                int middle = (end + start) / 2;

                MergeSort(array, start, middle);
                MergeSort(array, middle + 1, end);

                MergeArray(array, start, middle, end);
            }
        }

        private static void MergeArray(int[] array, int start, int middle, int end)
        {
            /* Create a temporary array for storing the merged array (Length of temp will be
             * the sum of the sizes of both arrays to be merged) */
            int[] temp = new int[end - start + 1];

            int leftHead = start;
            int rightHead = middle + 1;
            int tempIndex = 0;

            // Traverse both arrays simultaneously and store the smallest element of both to temp
            while (leftHead <= middle && rightHead <= end)
            {
                if (array[leftHead] < array[rightHead])
                {
                    temp[tempIndex] = array[leftHead];
                    leftHead++;
                }
                else
                {
                    temp[tempIndex] = array[rightHead];
                    rightHead++;
                }

                tempIndex++;
            }

            // If any elements remain in the left array add them to temp
            while (leftHead <= middle)
            {
                temp[tempIndex] = array[leftHead];
                tempIndex++;
                leftHead++;
            }

            // If any elements remain in the right array add them to temp
            while (rightHead <= end)
            {
                temp[tempIndex] = array[rightHead];
                tempIndex++;
                rightHead++;
            }

            // Copy all elements from temp to the original array
            tempIndex = 0;
            leftHead = start;

            while (tempIndex < temp.Length && leftHead <= end)
            {
                array[leftHead] = temp[tempIndex];
                leftHead++;
                tempIndex++;
            }
        }
    }
}