using System;

class Program
{


    static void MergeSort(int[] aArray)
    {
        int n = aArray.Length;
        int half = (n / 2);


        int[] bArray = new int[half];
        int[] cArray = new int[n - half];

        if (n > 1)
        {
            for (int b = 0; b < half; b++)
            {
                bArray[b] = aArray[b];

            }
            for (int c = 0; c < n - half; c++)
            {
                cArray[c] = aArray[c + half];
            }


            MergeSort(bArray);
            MergeSort(cArray);
            Merge(bArray, cArray, aArray, half, n);
        }

    }

    static void Merge(int[] bArray, int[] cArray, int[] aArray, int half, int n)
    {
        int i = 0;
        int j = 0;
        int k = 0;

        while ((i < half) && (j < n - half))
        {
            if (bArray[i] <= cArray[j])
            {
                aArray[k] = bArray[i];
                i++;
            }
            else
            {
                aArray[k] = cArray[j];
                j++;
            }

            k++;

            if (i == half)
            {
                aArray[k] = cArray[j];
            }
            else
            {
                aArray[k] = bArray[i];
            }

        }

    }

    static void Main()
    {
        int[] myArray = { 8, 3, 2, 9, 7, 1, 5, 4 };

        MergeSort(myArray);

        foreach (int item in myArray)
        {
            Console.Write("{0} ", item);
        }
        Console.WriteLine();


    }

}