前面我们讲了堆排序，因为它用到了完全二叉树所以效率 比较高。不过堆结构的设计本身是比较复杂的，老实说，能想出这样的结构就挺不容易 ， 有没有更直接简单的办法利用完全二叉树来排序呢?当然有。
为了更清晰地说清楚这里的思想，大家来看图 9-8-1 所示，我们将本是无序的数组序列 {16,7,13,10,9,15,3,2,5,8,12,1,11,4,6,14} ，通过两两合并排序后再合井，最终获得了 一个有序的数组。注意仔细观察它的形状，你会发现 ， 它像极了一棵倒置的完全二叉树，通常涉及到完全二叉树结构的排序算法，效率一般都不低的一一这就是我们要讲的归并排序法。
归并排序是创建在归并操作上的一种有效的排序算法，效率为O(nlogn)，1945年由冯·诺伊曼首次提出。
归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。
归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作，归并操作步骤如下：
实现
1 // 递归实现的归并排序(自顶向下（树）) 2 public static void mergeSort(int[] array, int start, int end) { 3 int len = end - start + 1; 4 if (len < 2) { 5 return; 6 } 7 int middle = (start + end) / 2; 8 mergeSort(array, start, middle); 9 mergeSort(array, middle + 1, end); 10 merge(array, start, middle, end); 11 } 12 13 // 非递归(迭代)实现的归并排序(自底向上（树）) 14 public static void mergeSort2(int[] array, int start, int end) { 15 int len = end - start + 1; 16 int mid; //子数组索引,前一个为a[start...mid]，后一个子数组为a[mid+1...end] 17 for(int i = 1; i < len; i *= 2){ // 子数组的大小i初始为1，每轮翻倍 18 start = 0; 19 while(start + i < len){ // 后一个子数组存在(需要归并) 20 mid = start + i - 1; 21 end = (mid + i < len) ? (mid + i) : (len - 1);//后一个子数组大小可能不够 22 merge(array, start, mid, end); //递归法的时候可以不往merge（）函数中传mid，但非递归法的时候必须传mid，因非递归方法mid不一定是（(start + end)/2） 23 start = end + 1; // 前一个子数组索引向后移动 24 } 25 } 26 } 27 28 //归并函数 29 // 合并两个已排好序的数组a[start...mid]和A[mid+1...end] 30 private static void merge(int[] array, int start, int mid, int end) { 31 int[] temp = new int[end - start + 1]; //辅助空间O(n) 32 int left = start; // 前一数组的起始元素 33 int right = mid + 1; // 后一数组的起始元素 34 int point = 0; 35 while (left <= mid && right <= end) { 36 if (array[left] <= array[right]) {// 带等号保证归并排序的稳定性 37 temp[point++] = array[left++];//++在后面，表示先运算，最后加1，不是先加1在运算 38 } else { 39 temp[point++] = array[right++]; 40 } 41 } 42 while (left <= mid) { //如果左指针还没到mid（即右指针已经遍历完右序列） 43 temp[point++] = array[left++]; 44 } 45 while (right <= end) { //如果右指针还没到mid（即左指针已经遍历完左序列） 46 temp[point++] = array[right++]; 47 } 48 for (int i = 0; i < temp.length; i++) {//把暂存数组里排好序的元素 写回到原数组 49 array[i + start] = temp[i]; 50 } 51 }
左侧中间的50，10也是分成单个元素序列然后再归并，只是这里没画出来。
时间复杂度：
最差时间复杂度 ---- O(nlogn)
最优时间复杂度 ---- O(nlogn)
平均时间复杂度 ---- O(nlogn)
空间复杂度：
空间复杂度为O(n)
稳定性：稳定
归并排序除了可以对数组进行排序，还可以高效的求出数组小和（即单调和）以及数组中的逆序对https://www.jianshu.com/p/3ab5033074f1
参考：
《大话数据结构》
http://www.cnblogs.com/eniac12/p/5329396.html
原文：https://www.cnblogs.com/xdyixia/p/9146384.html