using System;

public class Program

{

    public static void Main()

    {

        int[] numbers = { 56, 78, 9, 76, 45,32,21, 54, 64 };

​

            Console.WriteLine("Unsorted Array");

​

            foreach (var item in numbers)

            {

                Console.Write("{0} ", item);

            }

​

            Sort(numbers, 0, numbers.Length - 1);

​

            Console.WriteLine("\nSorted Array");

​

            foreach (var item in numbers)

            {

                Console.Write("{0} ", item);

            }

​

    }

     public static void Sort(int[] arr, int left, int right)

        {

            if (left < right)

            {

                int middle = (left + right) / 2;

                Sort(arr, left, middle);

                Sort(arr, middle + 1, right);

                Merge(arr, left, middle, right);

            }

        }

​

        private static void Merge(int[] arr, int left, int middle, int right)

        {

            int i = left;

            int j = middle + 1;

            int k = left;

​

            int[] temp = new int[arr.Length];

​

            while (i <= middle && j <= right)

            {

                if (arr[i] < arr[j])

                {

                    temp[k] = arr[i];

                    i++;

                    k++;

                }

                else

                {

                    temp[k] = arr[j];

                    j++;

                    k++;

                }

            }

            while (i <= middle)

            {

                temp[k] = arr[i];

                i++;

                k++;

            }

​

            while (j <= right)

            {

                temp[k] = arr[j];

                j++;

                k++;

            }

​

            for (int p = left; p <= right; p++)

            {

                arr[p] = temp[p];

            }

​

        }

}