using System;

public class Program

{

    static void MergeSort(int[] arr)

    {

        if(arr.Length <= 1) return;

        int leftLength = arr.Length / 2;

        int rightLength = arr.Length - leftLength;

        int[] leftArray = new int[leftLength];

        int[] rightArray = new int[rightLength];

        Array.Copy(arr, 0 , leftArray , 0, leftLength);

        Array.Copy(arr, leftLength, rightArray, 0 , rightLength);

        MergeSort(leftArray);

        MergeSort(rightArray);

        MergeSortArray(arr, leftArray, rightArray);

    }

    static void MergeSortArray(int[] sort, int[] leftArr, int[] rightArr){

        int s=0,l=0,r=0;

        while(l<leftArr.Length && r < rightArr.Length)

        {

            sort[s++] = leftArr[l] < rightArr[r] ? leftArr[l++] : rightArr[r++];

        }

        while(l<leftArr.Length)

        {

            sort[s++] = leftArr[l++];

        }

        while(r < rightArr.Length)

        {

            sort[s++] = rightArr[r++];

        }

    }

    public static void Main()

    {

        int[] input = new int[]{8,2,7,4,9,1,0,5,6};

        Console.WriteLine(string.Join(",", input));

        MergeSort(input);   

        Console.WriteLine("Sorted Array" + string.Join(",", input));

    }

}