基本思想:将两个(或两个以上)有序表合并成一个新的有序表。

/// <summary>
        /// 归并排序 递归版本
        /// 将两个(或两个以上)有序表合并成一个新的有序表
        /// </summary>
        private static void MergeSort(int[] arr, int length)
        {
            int[] temp = new int[length];
            MergeInternalSort(arr, 0, length, temp);
        }

        private static void MergeInternalSort(int[] arr, int first, int last, int[] temp)
        {
            if (first < last)
            {
                int mid = (first + last) / 2;
                MergeInternalSort(arr, first, mid, temp);
                MergeInternalSort(arr, mid + 1, last, temp);
                Merge(arr, first, mid, last, temp);
            }
        }

       private static void Merge(int[] arr, int first, int mid, int last, int[] temp)
        {
                int i = first;
                int j = mid + 1;
                int k = 0;
                //通过比较,把较小的一部分数放入到temp数组中
                while (i <= mid && j <= last)
                {
                    if (arr[i] < arr[j])
                    {
                        temp[k++] = arr[i++];
                    }
                    else
                    {
                        temp[k++] = arr[j++];
                    }
                }
                //将数组剩余的数放入到temp数组中
                while (i <= mid)
                {
                    temp[k++] = arr[i++];
                }
                while (j <= last)
                {
                    temp[k++] = arr[j++];
                }
                //把合并的数组结果赋值给原数组
                for (int m = 0; m < k; m++)
                {
                    arr[m + first] = temp[m];
                }
         }