using System;

public class Program

{

    public static void Main()

    {

        int[] array = new int[] {6, 7, 3, 2, 1, 9, 4};

        MergeSort(array);

        for(int i = 0; i < array.Length; i++)

        {

            Console.WriteLine(array[i]);

        }

    }

    public static void MergeSort(int[] array)

    {

        MergeSort(array, new int[array.Length], 0, array.Length - 1);

    }

    public static void MergeSort(int[] array, int[] temp, int leftStart, int rightEnd)

    {

        Console.WriteLine("MergeSort Left Start: {0}, Right End: {1}", leftStart, rightEnd);

        if(leftStart >= rightEnd)

            return;

        int middle = (leftStart + rightEnd) /2;

        MergeSort(array, temp, leftStart, middle);

        MergeSort(array, temp, (middle + 1), rightEnd);

        MergeHalves(array, temp, leftStart, rightEnd);

    }

    public static void MergeHalves(int[] array, int[] temp, int leftStart, int rightEnd)

    {

        Console.WriteLine("MergeHalves Left Start: {0}, Right End: {1}", leftStart, rightEnd);

        int leftEnd = (leftStart + rightEnd)/2;

        int rightStart = leftEnd + 1;

        int size = rightEnd - leftStart + 1;

        int left = leftStart;

        int right = rightStart;

        int index = leftStart;

        while (left <= leftEnd && right <= rightEnd)

        {

            if(array[left] <= array[right])

            {

                temp[index] = array[left];

                left++;

            }

            else

            {

                temp[index] = array[right];

                right++;

            }

            index++;

​

        }

        Array.Copy(array, left, temp, index, leftEnd - left + 1);

        Array.Copy(array, right, temp, index, rightEnd - right + 1);

        Array.Copy(temp, leftStart, array, leftStart, size);

    }

}