using System;

public class Program

{

    public static void Main()

    {

        sort(new int[] {0,2,5,3,4,7});

    }

    private static int[] sort(int[] array) {

        Console.WriteLine("Sorting iteration");

        if (array.Length == 1) {

            Console.WriteLine("Single element: " + array[0]);

            Console.WriteLine();

            return array;

        }

        Console.WriteLine("Array length: " + array.Length);

        Console.WriteLine("Incoming array: ");

        foreach(var v in array) {

            Console.Write(v + " ");

        }

        Console.WriteLine();        

        var length = array.Length/2;

        Console.WriteLine("Middle: " + length);

        int[] arr1 = new int[length];

        Array.Copy(array, 0, arr1, 0, length);

        Console.WriteLine("arr1:");

        foreach(var n in arr1) {

            Console.Write(n + " ");

        }

        Console.WriteLine();

        int[] arr2 = new int[array.Length - length];

        Array.Copy(array, length, arr2, 0, array.Length - length);

        Console.WriteLine("arr2:");

        foreach(var n in arr2) {

            Console.Write(n + " ");

        }

        Console.WriteLine();

        Console.WriteLine("Sorting arr1");

        arr1 = sort(arr1);

        Console.WriteLine("Sorting arr2");

        arr2 = sort(arr2);

        Console.WriteLine("Merging sort results.");

        Console.Write("Sorter arr1: ");

        foreach (var n in arr1) {

            Console.Write(n + " ");

        }

        Console.WriteLine();

        Console.Write("Sorter arr2: ");

        foreach (var n in arr2) {

            Console.Write(n + " ");

        }

        Console.WriteLine();

        int i = 0;

        int j = 0;

        int[] result = new int[array.Length];

        while (i < arr1.Length && j < arr2.Length) {

            Console.WriteLine(string.Format("i: {0}; arr1[i]: {2}; j: {1}; arr2[j]: {3}", i, j, arr1[i], arr2[j]));

            if (arr1[i] < arr2[j]) {

                Console.WriteLine(string.Format("result[{0}] = arr1[{1}] = {2}", i+j, i, arr1[i]));

                result[i+j] = arr1[i];

                i++;

            }

            else {

                Console.WriteLine(string.Format("result[{0}] = arr2[{1}] = {2}", i+j, j, arr2[j]));

                result[i+j] = arr2[j];

                j++;

            }

            if (i == arr1.Length) {

                Console.WriteLine("arr1 end.");

                for (int k = j; k < arr2.Length; k++) {

                    Console.WriteLine(string.Format("result[{0}] = arr2[{1}] = {2}", i+k, k, arr2[k]));

                    result[i+k] = arr2[k];

                }

            }

            else if (j == arr2.Length) {

                Console.WriteLine("arr2 end.");

                for (int k = i; k < arr1.Length; k++) {

                    Console.WriteLine(string.Format("result[{0}] = arr1[{1}] = {2}", j+k, k, arr1[k]));

                    result[j+k] = arr1[k];

                }

            }

        }

        Console.WriteLine("Sorting result:");

        foreach(var n in result) {

            Console.Write(n + " ");

        }

        Console.WriteLine();

        Console.WriteLine();

        return result;

    }

}