常见算法（五）归并排序

归并排序思路：

1、将数组进行分组，先将每个分组之内的数进行排序。

2、将几个分组进行合并，形成中级分组，再进行排序

3、将所有中型分组进行合并，再进行排序

也就是 排序--合并--排序--合并--...

 代码实现如下：

int[] arr = { 1, 9, 2, 6, 3, 2, 5 };

            int mid = (arr.Length + 1) / 2 == 0 ? (arr.Length + 1) / 2 : arr.Length / 2;
            List<int> Left = new List<int>();
            List<int> Right = new List<int>();

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

            for (int i = 0; i <= mid; i++) Left.Add(arr[i]);
            for (int j = mid+1; j < arr.Length; j++) Right.Add(arr[j]);

            Left.Sort();
            Right.Sort();

            final= Merge(Left, Right);

static List<int> Merge(List<int>left, List<int> right)
        {
            List<int> result = new List<int>();
            //result始终添加最小值，并且删除第0个元素，达到更新集合的目的
            while(left.Count>0 && right.Count > 0)
            {
                if (left[0] < right[0])
                {
                    result.Add(left[0]);
                    left.RemoveAt(0);
                }
                else
                {
                    result.Add(right[0]);
                    right.RemoveAt(0);
                }
            }
            
            //此时肯定只有一个集合里面还有数，而且还是有序的，那么直接添加即可
            if (left.Count > 0)
            {
                for (int i = 0; i < left.Count; i++) result.Add(left[i]);
            }
            if (right.Count > 0)
            {
                for (int i = 0; i < right.Count; i++) result.Add(right[i]);
            }
            return result;
        }