1. 基本思想

①Divide array into two halves.
②Recursively sort each half.
③Merge two halves.
将数组分成两部分，两部分分别排好序，最后将两个有序的子数组整合成一个有序的数组。

归并排序

注意：input数组是归并排序需要的额外空间。results数组是输入数组排序后的结果。

    // stably merge a[lo .. mid] with a[mid+1 ..hi] using aux[lo .. hi]
    private static void merge(Comparable[] a, Comparable[] aux, int lo, int mid, int hi) {
        // precondition: a[lo .. mid] and a[mid+1 .. hi] are sorted subarrays
        assert isSorted(a, lo, mid);
        assert isSorted(a, mid+1, hi);
        // copy to aux[]
        for (int k = lo; k <= hi; k++) {
            aux[k] = a[k]; 
        }
        // merge back to a[]
        int i = lo, j = mid+1;
        for (int k = lo; k <= hi; k++) {
            if      (i > mid)              a[k] = aux[j++];
            else if (j > hi)               a[k] = aux[i++];
            else if (less(aux[j], aux[i])) a[k] = aux[j++];
            else                           a[k] = aux[i++];
        }
        // postcondition: a[lo .. hi] is sorted
        assert isSorted(a, lo, hi);
    }

2. 自顶向下的归并排序

Code

 // mergesort a[lo..hi] using auxiliary array aux[lo..hi]
    private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi) {
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, aux, lo, mid);
        sort(a, aux, mid + 1, hi);
        merge(a, aux, lo, mid, hi);
    }
//调用方法   
    public static void sort(Comparable[] a) {
        Comparable[] aux = new Comparable[a.length];
        sort(a, aux, 0, a.length-1);
        assert isSorted(a);
    }

Example
top-down归并排序
要理解递归调用的次序：

3.分析
①长度为N的数组使用归并排序最多需要NlgN次比较。每次归并最多N次比较，最少N/2次比较。
C (N) ≤ C (⎡N / 2⎤) + C (⎣N / 2⎦) + N for N > 1, with C (1) = 0

②长度为N的数组自顶向下归并排序最多需要访问数组6NlgN次。
每次归并需要aux[k] = a[k]最多访问2N次数组，每次归并最多进行N次比较，每次比较访问2个元素，比较共2N次访问数组，最后将排好序的结果拷贝到原始数组中a[k] = aux[XX]需要2N次访问数组。
③归并排序需要N个额外的存储空间。

3. 自底向上的归并排序

Code

 public static void sort(Comparable[] a) {
        int n = a.length;
        Comparable[] aux = new Comparable[n];
        //len代表子数组的大小
        for (int len = 1; len < n; len *= 2) {
            for (int lo = 0; lo < n-len; lo += len+len) {
                int mid  = lo+len-1;
                int hi = Math.min(lo+len+len-1, n-1);
                merge(a, aux, lo, mid, hi);
            }
        }
        assert isSorted(a);
    }