阐述：

归并排序是将两个有序表合并成新的有序表；

而子序列的划分是递归地将待排序集合折半划分多个子序列，类似一个二叉树，

另外上面的递归操作大多会涉及分治思想，通俗讲就是各个分支上的子序列的有序，为最大的序列的有序埋下基础。

所以需要lgN趟的二路合并（假设集合的规模是N），每趟合并的复杂度是O(N)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(N*lgN)。

归并排序在划分子序列，二路合并有序集合时并没有改变两个相同元素的相对位置，故而是稳定的。

但是，归并排序需要额外的临时存储空间来暂存归并好的结果，所以空间复杂度是O(N)。

归并排序的关键字是：有序集合的合并；子序列的划分方式（如二路归并是通过递归地折半划分）

效果图：

大家可以看到处理每一趟归并的走位，就像我们遍历二叉树的顺序。

代码（c#）：

/// 
        /// 归并排序入口        /// 
        public static void DoMergeSort_Entrance()        {            List
     
       listNum = new List
      
       () { 25, 19, 6, 58, 34, 10, 7, 98, 160, 0 };            DoMergeSort_Sort(listNum, 0, listNum.Count - 1);        }        /// 
       
        /// 归并排序， 排序方法，递归调用，看到下面的递归过程，会联想到二叉树的遍历        /// 
        public static void DoMergeSort_Sort(List
       
         listNum, int indexStart, int indexEnd)        {            //LogWrite.LogPlain(DisplayListLimitIndex(listNum, indexStart, indexEnd));            if (indexStart == indexEnd) //递归终止的条件            {                return;            }            else            {                int indexMiddle = (indexStart + indexEnd) / 2;                //递归遍历左子树，直到左子树叶子节点                DoMergeSort_Sort(listNum, indexStart, indexMiddle);                //递归遍历右子树，直到右子树叶子节点                DoMergeSort_Sort(listNum, indexMiddle + 1, indexEnd);                //将由indexMiddle分割开来的有序左右集合归并起来                DoMergeSort_Merge(listNum, indexStart, indexMiddle, indexEnd);            }        }        /// 
        
        /// 归并排序，归并方法，将索引划分出来的两个集合归并，需要用到额外的存储空间存放归并的结果        /// 
        public static void DoMergeSort_Merge(List
        
          listNum, int indexStart, int indexMiddle, int indexEnd)        {            List
         
           listTemp = new List
          
           (listNum.Count); listNum.ForEach(item => { listTemp.Add(item); }); int indexLeft = indexStart; //左集合活动索引 int indexRight = indexMiddle + 1;//右集合活动索引 int indexTemp = indexStart;//临时数组活动索引 //遍历两个集合，然后比较大小，较小的放置到临时数组中 while (indexLeft <= indexMiddle && indexRight <= indexEnd) { if (listNum[indexLeft] <= listNum[indexRight]) { listTemp[indexTemp++] = listNum[indexLeft++]; } else { listTemp[indexTemp++] = listNum[indexRight++]; } } //左右两个集合，有可能有一个集合还剩余，将剩余的部分放到临时数组中 if (indexLeft <= indexMiddle) { while (indexLeft <= indexMiddle) { listTemp[indexTemp++] = listNum[indexLeft++]; } } else { if (indexRight <= indexEnd) { while (indexRight <= indexEnd) { listTemp[indexTemp++] = listNum[indexRight++]; } } } //最后将临时结果反存到数组中 listNum.Clear(); listTemp.ForEach(item => { listNum.Add(item); }); //LogWrite.LogPlain(DisplayListLimitIndex(listNum, indexStart, indexEnd, '<', '>')); }