using System;
using System.Collections.Generic;

namespace merge_sort
{
    public static class Sort
    {
        public static void Merge_sort(int[] array, int left, int right, int[] temp)
        {
            if (left < right)
            {
                int mid = (int)((left + right) / 2);
                Merge_sort(array, left, mid, temp);
                Merge_sort(array, mid + 1, right, temp);

                int l1 = left;
                int r1 = mid;//第一个有序序列
                int l2 = mid + 1;
                int r2 = right;//第二个有序序列
                //这两个序列本身就是相邻的
                int k = 0;

                //下面代码是将 两个有序序列合并，并使合并后的序列仍然有序
                while (l1 <= r1 && l2 <= r2)
                {
                    if (array[l1] <= array[l2])
                    {
                        temp[k++] = array[l1++];
                    }
                    else
                    {
                        temp[k++] = array[l2++];
                    }
                }
                while (l1 <= r1)
                {
                    temp[k++] = array[l1++];
                }
                while (l2 <= r2)
                {
                    temp[k++] = array[l2++];
                }
                for (int i = 0; i < k; i++)
                {
                    array[left + i] = temp[i];
                }
            }
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            Random m = new Random();
            List<int> list = new List<int>();
            for (int i = 0; i < 20000000; i++)
            {
                list.Add(m.Next(10000));
            }
            int[] array = list.ToArray();
            int[] temp = new int[array.Length];
            DateTime b_time = DateTime.Now;
            b_time = DateTime.Now;
            Sort.Merge_sort(array, 0, array.Length - 1, temp);
            DateTime a_time = DateTime.Now;
            TimeSpan time = a_time.Subtract(b_time);
            Console.WriteLine(time);
        }
    }
}

以2000万个0～9999的随机数进行测试：

00:00:07.2676490

Press any key to continue...

    归并排序，什么是归并排序？
    百度百科定义：归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
    下面用通俗易懂的语言来描述该算法，归并排序算法是一个自下而上的排序算法，先使子序列有序，然后合并两个相邻子序列，并使得到的序列仍然有序，这样逐级向上归并，最终达到使整个序列有序的目的。
    同时归并排序算法还有一个任务，即分割序列，因为我们得到的无序序列是一个整体，我们需要将它分割开，以供归并操作使用。
    下面讲解算法实现部分：
    一：向Merge_sort函数传递要排序的序列array；
    二：Merge_sort函数使用二分法将array分割成两个子序列array[0:mid+1]和array[mid+1:length],并同时对两个子序列使用Merge_sort函数进行递归。由此引申出对Merge_sort函数参数的讨论，首先它需要array，其次需要所要排序部分的区间，即left和right。
    三：此时已经实现了将序列自上而下进行了分割，还未对序列进行自下而上的归并。所以应该在分割完成之后进行归并，且是每一次分割完成之后都需要使用Merge函数归并。即可得到下述代码：

Merge_sort(array, left, right)
{
        mid = (left + right) / 2;
        Merge_sort(array, left, mid);
        Merge_sort(array, mid + 1, right);
        Merge(array, left, mid, mid+1, right);
}

    四：上述代码缺少递归结束条件，当所要排序的序列只有1个项时，应返回。故可用if left!=right 或者left<right。即可得到下述代码：

Merge_sort(array, left, right)
{
        if (left < right)
        {
                mid = (left + right) / 2;
                Merge_sort(array, left, mid);
                Merge_sort(array, mid + 1, right);
                Merge(array, left, mid, mid+1, right);
        }
}

    五：在Merge函数中，是将两个有序序列合并成一个有序序列的操作。根据归并的定义，它需要一个辅助空间，这个辅助空间大小是两个子序列项数之和的长度。根据递归方式，我们需要为它一个最大长度，使之在排序算法整个运行周期中保持合理大小。通过分析可以发现，他的最大长度恰恰是原无序array的长度。而这个辅助空间是贯穿整个归并排序算法的。所以可以得到下述代码：

Merge_sort(array, left, right, assist)
{
        if (left < right)
        {
                mid = (left + right) / 2;
                Merge_sort(array, left, mid, assist);
                Merge_sort(array, mid + 1, right, assist);
                Merge(array, left, mid, mid+1, right, assist);
        }
}

    本段代码与本文C#代码是一致的，本文代码将Merge函数直接实现在了Merge_sort函数中，在实际任务时可能带来某些不便，但仅仅对于学习而言，并无影响。