using System;

public class Program

{

    public static void Main()

    {

        TestMergeSort(new int[]{1,5,3,2,6,3,2,4,82,45,13,29,10,22,1,2,56,7,14,24,74,34,1,4,7,2,5,1,6,2,4}); 

    }

    public static void TestMergeSort(int[] nums){

        var unsorted = "";

        foreach(var num in nums){

            unsorted += "," + num;

        }

        var results = MergeSort(nums);

        var sorted = "";

        foreach(var result in results){

            sorted += "," + result;

        }

        Console.WriteLine(unsorted);

        Console.WriteLine(sorted);

    }

    public static int[] MergeSort(int[] nums){

      if(nums.Length == 1){

        return nums;

      }

      var half = nums.Length/2;

      return Merge(

        MergeSort(GetSubArray(nums, 0, half)),

        MergeSort(GetSubArray(nums, half, nums.Length-half))

      );   

    }

    public static int[] Merge(int[] left, int[] right){

      var sorted = new int[left.Length + right.Length];

      var leftIndex=0;

      var rightIndex=0;

      for(var i=0; i< left.Length+right.Length; i++){

        var leftVal = leftIndex < left.Length ? left[leftIndex] : int.MaxValue;

        var rightVal = rightIndex < right.Length ? right[rightIndex] : int.MaxValue;

        if(leftVal<rightVal){

          sorted[i] = leftVal;

          leftIndex++;

        }

        else{

          sorted[i] = rightVal;

          rightIndex++;

        }

      }

      return sorted;

    }

    public static int[] GetSubArray(int[] original, int index, int length)

    {

        var newArray = new int[length];

        Array.Copy(original, index, newArray, 0, length);

        return newArray;

    }

​

}