一、基本思想
归并排序是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将一个数组分为越来越小的子列表，每个子列表单独进行排序，然后合并形成更大的有序列表。
通过归并子列表元素来合并子列表就是归并排序（Merge Sort）
二、算法描述
1. 将一个列表分割成2个子列表
2. 第1个列表调用索引[first,mid]来定义原始序列的下半部分；
3. 第2个列表调用索引[mid,last]来定义原始序列的上半部分；
4. 这个过程可以生成一个递归调用链，从而将原始列表分隔为越来越小的子列表(半部分列表)，直至这些子列表长度为1（停止条件）
5. 以相反的顺序合并这些子列表，会形成越来越大的子列表；
6. 子列表的最后合并对应着第一个递归步骤，并且将原始数组排列为有序状态。
三、示例代码
public class Merge{ public static void MergeSort(int[] arr) { // create a temporary array to store partitioned elements int[] tempArr = (int[])arr.Clone(); // call msort with arrays arr and tempArr along with the index range msort(arr, tempArr, 0, arr.Length); } private static void msort(int[] arr, int[] tempArr, int first, int last) { // if the sublist has more than 1 element,continue if (first + 1 < last) { // if the sublist of size 2 or more,call msort() // for the left and right sublists and then merge the sorted sublists using merge() int midpt = (first + last) / 2; msort(arr, tempArr, first, midpt); msort(arr, tempArr, midpt, last); // if list is already sorted,just copy from src to dest; // this is an optimization that results in faster sorts for nearly ordered list if (((IComparable)arr[midpt - 1]).CompareTo(arr[midpt]) < 0) { return; } // the element in the ranges[first,mid] and [mid,last] are ordered; // merge the ordered sublists into an ordered sequence in the range [first,last] // using the temporary array int indexA, indexB, indexC; // set indexA to scan sublist A with range[first,mid] // and indexB to scan sublist B with range[mid,last] indexA = first; indexB = midpt; indexC = first; // while both sublists are not exhausted, compare arr[indexA] and arr[indexB]; // copy the smaller to tempArr while (indexA < midpt && indexB < last) { if (((IComparable)arr[indexA]).CompareTo(arr[indexB]) < 0) { tempArr[indexC] = arr[indexA];// copy to tempArr indexA++; } else { tempArr[indexC] = arr[indexB];// copy to tempArr indexB++; } // increment indexC indexC++; } // copy the tail of the sublist that is not exhausted while (indexA < midpt) { tempArr[indexC] = arr[indexA];// copy to tempArr indexA++; indexC++; } while (indexB < last) { tempArr[indexC] = arr[indexB];// copy to tempArr indexB++; indexC++; } // copy the elements from temporary array to original array for (int i = first; i < last; i++) { arr[i] = tempArr[i]; } } }} 四、效率分析
稳定
空间复杂度：O(n)
时间复杂度：O(nlog2n)
最坏情况：O(nlog2n)
最好情况：O(nlog2n)