MergeSort Algorithm in C# (middle)

class MergeSort
    {

        public static List<int> Execute(List<int> list)
        {
            if (list.Count <= 1) { return list; }

            //Find the middle point
            int middle = list.Count / 2;

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

            //Divide the list from the middle
            for (int i=0;i<middle;i++)
            {
                left.Add(list[i]);
            }

            for (int i=middle;i<list.Count;i++)
            {
                right.Add(list[i]);
            }

            //Recursion to keep dividing and sorting.
            left = Execute(left);
            right = Execute(right);

            //This indicates that sorting is done.
            if (left[left.Count-1] < right[0])
            {
                left.AddRange(right);
                return left;
            }

            //If sorting is not done... Merge
            var result = Merge(left, right);

            return result;
        }

        private static List<int> Merge(List<int> left, List<int> right)
        {
            var result = new List<int>();

            while (left.Count > 0 && right.Count > 0)
            {
                //Sort into another list by comparison.
                if (left[0] < right[0])
                {
                    result.Add(left[0]);
                    left.RemoveAt(0);
                }
                else
                {
                    result.Add(right[0]);
                    right.RemoveAt(0);
                }
            }

            return result;
        }
    }

Comments

Popular posts from this blog

Tutorial: Using Google Cloud Storage from C# and .NET

Late 2008 Macbook only giving 1.5 gb/s speed with 6 gb/s Intel SSD?

The ridiculous interview experience