MergeSort

using System;
using System.Collections.Generic;


namespace _13.MergeSort
{
    /*
      Write a program that sorts an array of integers using the merge sort algorithm
     (find it in Wikipedia).
     Top-down implementation from wikipedia:
     http://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation
     */

    class Program
    {
        static void Main(string[] args)
        {
            List<int> listToSort = new List<int>();
            InitiliazeListRandomly(listToSort, 10);
            Console.WriteLine("\nInitial list.\n");
            PrintList(listToSort);

            listToSort = PerformMergeSort(listToSort);
            Console.WriteLine("\nSorted list.\n");
            PrintList(listToSort);
        }

        private static List<int> PerformMergeSort(List<int> listToSort)
        {
            //List of one element is sorted.
            if (listToSort.Count<=1)
            {
                return listToSort;
            }

            List<int> leftList = new List<int>(), rightList = new List<int>();
            int middle = listToSort.Count / 2;

            for (int elementIndex = 0; elementIndex < middle; elementIndex++)
            {
                leftList.Add(listToSort[elementIndex]);
            }

            for (int elementIndex = middle; elementIndex < listToSort.Count; elementIndex++)
            {
                rightList.Add(listToSort[elementIndex]);
            }

            //Recursively create new lists of have size the list passed as parameter.
            leftList = PerformMergeSort(leftList);
            rightList = PerformMergeSort(rightList);

            return MergeLeftAndRightList(leftList, rightList);
        }

        private static List<int> MergeLeftAndRightList(List<int> leftList, List<int> rightList)
        {
            List<int> mergedList = new List<int>();
            while (leftList.Count > 0 || rightList.Count > 0)
            {
                if (leftList.Count > 0 && rightList.Count > 0)
                {
                    //after "leftList.RemoveAt(0);" the next item becomes with index 0.
                    //So if list is: {1, 2}; after "RemoveAt(0)" list is {1} - the first
                    // element is 1.
                    if (leftList[0]<= rightList[0])
                    {
                        mergedList.Add(leftList[0]);
                        leftList.RemoveAt(0);
                    }
                    else
                    {
                        mergedList.Add(rightList[0]);
                        rightList.RemoveAt(0);
                    }
                }

                else if (leftList.Count >0)
                {
                    mergedList.Add(leftList[0]);
                    leftList.RemoveAt(0);
                }

                else if (rightList.Count > 0)
                {
                    mergedList.Add(rightList[0]);
                    rightList.RemoveAt(0);
                }

            }

            return mergedList;
        }

        /// <summary>
        /// Initializes list of integers.
        /// </summary>
        /// <param name="elementsList">The list to be initialized.</param>
        /// <param name="count">The number of the elements in the list.</param>
        private static void InitiliazeList(List<int> elementsList, int count)
        {
            for (int i = 0; i < count; i++)
            {
                Console.Write("Enter value {0}: ", i + 1);
                string currentNumber = Console.ReadLine();
                int currentElement = int.Parse(currentNumber);

                elementsList.Add(currentElement);
            }
        }

        /// <summary>
        /// Initializes list of integers by using random number generator.
        /// </summary>
        /// <param name="elementsList">The list to be initialized.</param>
        /// <param name="count">The number of the elements in the list.</param>
        private static void InitiliazeListRandomly(List<int> elementsList, int count)
        {
            Random numGenerator = new Random();
            for (int i = 0; i < count; i++)
            {
                int currentElement = numGenerator.Next(-561, 400);
                elementsList.Add(currentElement);
            }
        }

        public static void PrintList<T>(List<T> list)
        {
            foreach (T item in list)
            {
                Console.Write(item + " ");
            }
            Console.WriteLine("\n---------------");
        }
    }
}