归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
归并排序的基本思想将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
综上可知：归并排序其实要做两件事：
（1）“分解”——将序列每次折半划分。
（2）“合并”——将划分后的序列段两两合并后排序。
我们先来考虑第二步，如何合并？
在每次合并过程中，都是对两个有序的序列段进行合并，然后排序。
这两个有序序列段分别为 a[low, mid] 和 a[mid+1, high]。
先将他们合并到一个局部的暂存数组temArr中，带合并完成后再将R2复制回R中。
为了方便描述，我们称 a[low, mid] 第一段，a[mid+1, high] 为第二段。
每次从两个段中取出一个记录进行关键字的比较，将较小者放入temArr中。最后将各段中余下的部分直接复制到R2中。
经过这样的过程，temArr已经是一个有序的序列，再将其复制回R中，一次合并排序就完成了。
时间复杂度 归并排序的形式就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的可以得出它的时间复杂度是O(n*log2n)。 空间复杂度 由前面的算法说明可知，算法处理过程中，需要一个大小为n的临时存储空间用以保存合并序列。 算法稳定性 在归并排序中，相等的元素的顺序不会改变，所以它是稳定的算法。 归并排序和堆排序、快速排序的比较 若从空间复杂度来考虑：首选堆排序，其次是快速排序，最后是归并排序。 若从稳定性来考虑，应选取归并排序，因为堆排序和快速排序都是不稳定的。 若从平均情况下的排序速度考虑，应该选择快速排序。
public static void sort(int[] a, int left, int right) { if (left >= right) return; int center = (left + right) >> 1; sort(a, left, center); sort(a, center + 1, right); merge(a, left, center, right); } public static void merge(int[] data, int left, int center, int right) { int[] tmpArr = new int[right+1]; int mid = center + 1; int index = left; // index记录临时数组的索引 int tmp = left; // 从两个数组中取出最小的放入中临时数组 while (left <= center && mid <= right) { tmpArr[index++] = (data[left] <= data[mid]) ? data[left++]: data[mid++]; } // 剩余部分依次放入临时数组 while (mid <= right) { tmpArr[index++] = data[mid++]; } while (left <= center) { tmpArr[index++] = data[left++]; } // 将临时数组中的内容复制回原数组 for (int i = tmp; i <= right; i++) { data[i] = tmpArr[i]; } System.out.println(Arrays.toString(data)); } public static void main(String[] args) { int[] a = { 57, 68, 59, 52, 72, 28, 96, 33 }; sort(a, 0, a.length-1); } /*运行结果： [57, 68, 59, 52, 72, 28, 96, 33] [57, 68, 52, 59, 72, 28, 96, 33] [52, 57, 59, 68, 72, 28, 96, 33] [52, 57, 59, 68, 28, 72, 96, 33] [52, 57, 59, 68, 28, 72, 33, 96] [52, 57, 59, 68, 28, 33, 72, 96] [28, 33, 52, 57, 59, 68, 72, 96] */ 使用数组返回值 public int[] MSort(int[] arr, int low, int high) { if (low >= high) return new int[] { arr[low] }; int mid = (low + high) / 2; int[] left = MSort(arr, low, mid); int[] right = MSort(arr, mid + 1, high); return mergeTwoList(left, right); } public int[] mergeTwoList(int[] A, int[] B) { int[] C = new int[A.length + B.length]; int k = 0; int i = 0; int j = 0; while (i < A.length && j < B.length) { if (A[i] < B[j]) C[k++] = A[i++]; else C[k++] = B[j++]; } while (i < A.length) C[k++] = A[i++]; while (j < B.length) C[k++] = B[j++]; return C; }
