将两个有序的数组归并成一个更大的有序数组，这个操作叫归并。根据这个操作于是就有了归并排序，归并排序有两种实现方式。

自顶向下的归并排序

自顶向下的归并采用了分治（divide-and-conquer）的思想（将问题分（divide）成一些小的问题然后递归求解，然后治（conquer）阶段将分的阶段得到的各答案拼接在一起，即分而治之）。

代码实现

  1. public class Merge {
  2.     private static Integer[] aux;
  4.     /**
  5.      * 初始化辅助数组和相应的上下限数值
  6.      *
  7.      * @param a
  8.      * @return
  9.      */
  10.     public static Integer[] sort(Integer[] a) {
  11.         aux = new Integer[a.length]; // 初始化辅助数组
  12.         sort(a, 0, a.length - 1);
  13.         return a;
  14.     }
  16.     /**
  17.      * 辅助函数：用于交换元素
  18.      *
  19.      * @param valueA
  20.      * @param valueB
  21.      * @return
  22.      */
  23.     public static Boolean less(Integer valueA, Integer valueB) {
  24.         return valueA < valueB;
  25.     }
  27.     /**
  28.      * 辅助函数：用于递归排序
  29.      *
  30.      * @param a
  31.      * @param lo
  32.      * @param hi
  33.      */
  34.     private static void sort(Integer[] a, int lo, int hi) {
  35.         if (hi <= lo) return; // 极端情况 hi == lo，此时只有一个元素不需要再递归排序。
  36.         int mid = lo + (hi - lo) / 2;
  37.         sort(a, lo, mid);
  38.         sort(a, mid + 1, hi);
  39.         merge(a, lo, mid, hi); // 合并代码
  40.     }
  42.     /**
  43.      * 将数组中左右已排好序的两边重新合并到一起。
  44.      *
  45.      * @param a
  46.      * @param lo
  47.      * @param mid
  48.      * @param hi
  49.      */
  50.     public static void merge(Integer[] a, int lo, int mid, int hi) {
  51.         int i = lo, j = mid + 1;
  52.         for (int k = lo; k <= hi; k++)
  53.             aux[k] = a[k];
  55.         for (int k = lo; k <= hi; k++)
  56.             if (i > mid) a[k] = aux[j++];
  57.             else if (j > hi) a[k] = aux[i++];
  58.                 // aux[j] 和 aux[i] 循环两两进行比较，看谁先到达终点，然后执行上面两个分支。
  59.             else if (less(aux[j], aux[i])) a[k] = aux[j++];
  60.             else a[k] = aux[i++];
  61.     }
  63.     public static void main(String[] args) {
  64.         Integer[] array1 = new Integer[10];
  66.         for(int i = 0; i < array1.length; i++) {
  67.             array1[i] = (int)Math.floor((Math.random() * 10) + 1);
  68.         }
  70.         System.out.println(Arrays.toString(array1)); // [7, 5, 3, 8, 6, 3, 1, 10, 6, 9]
  71.         System.out.println(Arrays.toString(sort(array1))); // [1, 3, 3, 5, 6, 6, 7, 8, 9, 10]
  72.     }
  73. }

自底向上归并排序

实现归并排序的另一种方法是先归并那些微型的数组，然后再成对归并得到子数组，如此这般，直到将整个数组归并在一起。

实现代码

  1. /**
  2.  * 自低向上归并排序
  3.  *
  4.  * @param a
  5. */
  6. public static Integer[] bUSort(Integer[] a) {
  7.     int N = a.length;
  8.     aux = new Integer[N];
  9.     for (int sz = 1; sz < N; sz = sz + sz) {
  10.         System.out.println("sz:" + sz);
  11.         // lo += sz + sz 因为是两两合并所以 sz + sz
  12.         // 数组长度 N 可能是奇数或者偶数
  13.         for (int lo = 0; lo < N - sz; lo += sz + sz) {
  14.             System.out.println("  lo: " + lo);
  15.             System.out.println("    lo+sz-1: " + (lo + sz - 1));
  16.             // Math.mi(lo+sz+sz-1, N-1) 兼容数组尾部的两两合并
  17.             merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
  18.         }
  19.     }
  20.     return a;
  21. }

参考：