using System;

public class Program

{

    public static void Main()

    {

        int[] input = new int[10] {8, 34, 9, 17, 1, 65, 23, 29, 6, 54};

        var result = MergeSort(input);

        Console.Write($"Final: ");

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

        {

            Console.Write(input[i] + " ");

        }

    }

    public static int[] MergeSort(int[] array)

    {

        int n = array.Length;

        Console.Write($"Array: ");

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

        {

            Console.Write($"{array[k]}" + " ");

        }

        Console.WriteLine("");

        if(n > 1)

        {

            int lSize = n/2;

            int rSize = n - n/2;

​

            Console.WriteLine($"MergeSort: lSize: {rSize}, rSize: {rSize}");

            int[] left = new int[lSize];

            int[] right = new int[rSize];

​

            int i = 0;

            int lIndex = 0;

            while(i < lSize)

            {

                left[lIndex] = array[i];

                lIndex++;

                i++;

            }

​

            int rIndex = 0;

            while(i < array.Length)

            {

                right[rIndex] = array[i];

                rIndex++;

                i++;

            }

​

            var newLeft = MergeSort(left);

            for(int k = 0; k < newLeft.Length; k++)

            {

                Console.Write($"NewLeft: {newLeft[k]}" + " ");

            }

            Console.WriteLine("");

            var newRight = MergeSort(right);

            for(int k = 0; k < newRight.Length; k++)

            {

                Console.Write($"NewRight: {newRight[k]}" + " ");

            }

            Console.WriteLine("");

            var interimResult = Merge(newLeft, newRight, array);

            Console.Write("Interim Result: ");

            for(int k = 0; k < interimResult.Length; k++)

            {

                Console.Write($"{interimResult[k]}" + " ");

            }

            Console.WriteLine("");

            return interimResult;

        }

        return array;

    }

    public static int[] Merge(int[] left, int[] right, int[] array)

    {

        int leftIndex = 0;

        int rightIndex = 0;

        int arrayIndex = 0;

        while(leftIndex < left.Length && rightIndex < right.Length)

        {

            if(left[leftIndex] < right[rightIndex])

            {

                array[arrayIndex] = left[leftIndex];

                leftIndex++;

            }

            else

            {

                array[arrayIndex] = right[rightIndex];

                rightIndex++;

            }

            arrayIndex++;

        }       

        if(leftIndex < left.Length)

        {

            for(int i = leftIndex; i<left.Length; i++)

            {

                array[arrayIndex] = left[leftIndex];

                leftIndex++;

                arrayIndex++;

            }

        }

        else

        {

            for(int i = rightIndex; i<right.Length; i++)

            {

                array[arrayIndex] = right[rightIndex];

                rightIndex++;

                arrayIndex++;

            }

        }

        return array;

    }

}