C# Code to implement Merge Sort

public static IList MergeSort(IList list)
        {
            if (list.Count <= 1)
                return list;

            int mid = list.Count / 2;

            IList leftPart = new ArrayList();
            IList rightPart = new ArrayList();

            for (int i = 0; i < mid; i++)
                leftPart.Add(list[i]);

            for (int i = mid; i < list.Count; i++)
                rightPart.Add(list[i]);

            return Merge(MergeSort(leftPart), MergeSort(rightPart));
        }

        public static IList Merge(IList leftPart, IList rightPart)
        {
            IList rv = new ArrayList();

            while (leftPart.Count > 0 && rightPart.Count > 0)
                if (((IComparable)leftPart[0]).CompareTo(rightPart[0]) > 0)
                {
                    rv.Add(rightPart[0]);
                    rightPart.RemoveAt(0);
                }
                else
                {
                    rv.Add(leftPart[0]);
                    leftPart.RemoveAt(0);
                }

            for (int i = 0; i < leftPart.Count; i++)
                rv.Add(leftPart[i]);

            for (int i = 0; i < rightPart.Count; i++)
                rv.Add(rightPart[i]);

            return rv;
        }

static void Main(string[] args)
        {
            Console.Write("Enter no. of elements: ");

            IComparable[] arr = new IComparable[int.Parse(Console.ReadLine())];

            Console.Write("Enter items: ");

            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = int.Parse(Console.ReadLine());
            }

            IList Result = MergeSort(arr.ToList());

            foreach (var x in Result)
                Console.Write(x +"\t");

            Console.Read();
        }