using System;

using System.Threading;

using System.Collections.Generic;

using System.Linq;

public class Program

{

    public static void Main()

    {

         List<int> unsorted = new List<int>();

            List<int> sorted;

​

            Random random = new Random();

​

            Console.WriteLine("Original array elements:" );

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

                unsorted.Add(random.Next(0,100));

                Console.Write(unsorted[i]+" ");

            }

            Console.WriteLine();

            DateTime dt =  DateTime.Now;

            sorted = MergeSort(unsorted);

            TimeSpan secondTime = DateTime.Now- dt;

            Console.WriteLine(secondTime.ToString());

            Console.WriteLine("Sorted array elements: ");

            foreach (int x in sorted)

            {

                Console.Write(x+" ");

            }

            Console.Write("\n");

​

    }

     private static List<int> MergeSort(List<int> unsorted)

        {

            if (unsorted.Count <= 1)

                return unsorted;

​

            List<int> left = new List<int>();

            List<int> right = new List<int>();

​

            int middle = unsorted.Count / 2;

            for (int i = 0; i < middle;i++)  //Dividing the unsorted list

            {

                left.Add(unsorted[i]);

            }

            for (int i = middle; i < unsorted.Count; i++)

            {

                right.Add(unsorted[i]);

            }

​

            left = MergeSort(left);

            right = MergeSort(right);

            return Merge(left, right);

        }

​

        private static List<int> Merge(List<int> left, List<int> right)

        {

            List<int> result = new List<int>();

​

            while(left.Count > 0 || right.Count>0)

            {

                if (left.Count > 0 && right.Count > 0)

                {

                    if (left.First() <= right.First())  //Comparing First two elements to see which is smaller

                    {

                        result.Add(left.First());

                        left.Remove(left.First());      //Rest of the list minus the first element

                    }

                    else

                    {

                        result.Add(right.First());

                        right.Remove(right.First());

                    }

                }

                else if(left.Count>0)

                {

                    result.Add(left.First());

                    left.Remove(left.First());

                }

                else if (right.Count > 0)

                {

                    result.Add(right.First());

​

                    right.Remove(right.First());    

                }    

            }

            return result;

        }

}