using System;

​

public class Program 

{

    public static void Main()

    {

        int[] input=new int[10];

        Random rnd=new Random();

        for(int i=0;i<input.Length;i++) {

            input[i]=rnd.Next(100);

        }

        for(int i=0;i<input.Length;i++) {

            Console.WriteLine(input[i]);

        } 

        MergeSort(input);

        Console.WriteLine("Sorted:");

        for(int i=0;i<input.Length;i++) {

            Console.WriteLine(input[i]);

        }

    }

    public static void MergeSort(int[] nums) {

        int numsLen=nums.Length;

        if(numsLen<2) return;

        int mid=numsLen/2;

        int[] leftArr=new int[mid];

        int[] rightArr=new int[numsLen-mid];

        for(int i=0;i<mid;i++){

            leftArr[i]=nums[i];

        }

        for(int i=mid;i<numsLen;i++) {

            rightArr[i-mid]=nums[i];

        }

        MergeSort(leftArr);

        MergeSort(rightArr);

        Merge(nums,leftArr,rightArr);

    }

    public static void Merge(int[] nums,int[] leftArr,int[] rightArr) {

        int lCnt=0,rCnt=0,iCnt=0;

        while(lCnt<leftArr.Length && rCnt<rightArr.Length)  {

            if(leftArr[lCnt]<=rightArr[rCnt]) {

                nums[iCnt++]=leftArr[lCnt++];

            }

            else {

                nums[iCnt++]=rightArr[rCnt++];

            }

        }

        while(lCnt<leftArr.Length) {

            nums[iCnt++]=leftArr[lCnt++];

        }

        while(rCnt<rightArr.Length) {

            nums[iCnt++]=rightArr[rCnt++];

        }

    }

}