using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace MegreSort
{
    class Program
    {
        static void Main(string[] args)
        {
            int[] A = { 8, 2, 1, 3, 5, 6, 4, 7, 9, 0 };
            //int[] A = { 8, 2, 1, 3 };
            PrintArray(A);
            int e = A.Length - 1;
            MergeSort(A, 0, e);
            PrintArray(A);
            System.Console.ReadKey();
        }

        private static void PrintArray(int[] A)
        {
            int count = A.Length;
            for (int i = 0; i < count; i++)
            {
                if (i == 0)
                    System.Console.Write(A[i].ToString());
                else if (i == (count - 1))
                    System.Console.Write(" " + A[i].ToString() + "\n");
                else
                    System.Console.Write(" " + A[i].ToString());
            }
        }

        private static void Merge(int[] A,int p,int q,int r)
        {
            int n1 = q - p + 1;
            int n2 = r - q;
            int[] L = new int[n1 + 1];
            int[] R = new int[n2 + 1];
            for(int i = 0;i < n1;i++)
            {
                L[i] = A[p + i];
            }
            for(int j = 0;j < n2;j++)
            {
                R[j] = A[q + j + 1];
            }
            L[n1] = int.MaxValue;
            R[n2] = int.MaxValue;
            int m = 0;
            int n = 0;
            for(int k = p;k <= r;k++)
            {
                if(L[m] <= R[n])
                {
                    A[k] = L[m];
                    m++;
                }
                else
                {
                    A[k] = R[n];
                    n++;
                }
            }
        }

        private static void MergeSort(int[] A, int p, int r)
        {
            if (p < r)
            {
                int q = (p + r) / 2;
                MergeSort(A, p, q);
                MergeSort(A, q + 1, r);
                Merge(A, p, q, r);
            }
        }
    }
}