MergeSortFinal

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

namespace MergeSort1
{
    class Program
    {
        static void Main(string[] args)
        {
            List<int> list = new List<int>();
            int m = int.Parse(Console.ReadLine());
            for (int i = 0; i < m; i++)
            {
                int p = int.Parse(Console.ReadLine());
                list.Add(p);
            }
            Console.WriteLine(String.Join(",", MergeSort(list)));
        }
        static List<int> MergeSort(List<int> array)
        {
            List<int> output = new List<int>();
            if (array.Count == 1)
            {
                return array;
            }
            if (array.Count == 2)
            {
                if (array[0] > array[1])
                {
                    int a = array[1];
                    array[1] = array[0];
                    array[0] = a;
                    return array;
                }
                else
                {
                    return array;
                }
            }
            else
            {
                List<int> firstList = new List<int>();
                List<int> secondList = new List<int>();
                for (int i = 0; i < array.Count / 2; i++)
                {
                    firstList.Add(array[i]);
                    secondList.Add(array[i + array.Count / 2]);
                }
                if (array.Count % 2 != 0)
                {
                    secondList.Add(array[array.Count - 1]);
                }
                firstList = MergeSort(firstList);
                secondList = MergeSort(secondList);
                int k = 0;
                int j = 0;
                int size = firstList.Count + secondList.Count;
                int markerFirst = firstList.Count;
                int markerSecond = secondList.Count;

                for (int i = 0; i < size; i++)
                {
                    if (k == markerFirst)
                    {
                        output.Add(secondList[j]);
                        j++;
                        continue;
                    }
                    if (j == markerSecond)
                    {
                        output.Add(firstList[k]);
                        k++;
                        continue;
                    }
                    if (firstList[k] < secondList[j])
                    {
                        output.Add(firstList[k]);
                        k++;
                    }
                    else
                    {
                        output.Add(secondList[j]);
                        j++;
                    }
                }
            }
            return output;
        }
    }
}