using System;

class Merges
{
    void sort(int[] array)
    {
        if (array.Length < 2)
        {
            return;
        }
        int middle = array.Length / 2;
        int[] left = new int[middle];
        int[] right = new int[array.Length - middle];

        for (int i = 0; i < middle; i++)
        {
            left[i] = array[i];
        }
        for (int i = middle; i < array.Length; i++)
        {
            right[i - middle] = array[i];
        }
        sort(left);
        sort(right);
        merge(array, left, right);
    }

    void merge(int[] res, int[] left, int[] right)
    {
        int index1 = 0;
        int index2 = 0;

        int result = 0;

        while (index1 < left.Length && index2 < right.Length)
        {
            if (left[index1] <= right[index2])
            {
                res[result] = left[index1];
                index1++;
            }
            else
            {
                res[result] = right[index2];
                index2++;
            }
            result++;
        }
        while (index1 < left.Length)
        {
            res[result] = left[index1];
            index1++;
            result++;
        }
        while (index2 < right.Length)
        {
            res[result] = right[index2];
            index2++;
            result++;
        }
    }


   static void print(int[] array)
    {
        int n = array.Length;
        for (int i = 0; i < n; ++i)
            Console.Write(array[i] + "");
        Console.WriteLine();
    }

    public static void Main(String[] ar)
    {
        int[] mass = { 11, 66, 44, 55, 77, 99, 22, 88, 33 };
        print(mass);
        Merges ob = new Merges();
        ob.sort(mass);
        Console.WriteLine("Got it!");
        print(mass);

    }
}