# 归并排序

归并排序的思想很简单。简单地说，要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。归并排序最吸引人的性质是它能够保证将任意长度为N的数组排序所需时间和NlogN成正比；它的主要缺点则是它所需的额外空间和N成正比。

# 原地归并的抽象方法

# 算法实现

public class MergeSort {
    public static void merge(Comparable[] a, int lo, int mid, int hi) {
        //将a[lo..mid]和a[mid+1..hi]归并
        int i = lo, j = mid + 1;
        for (int k = lo; k <= hi; k++) //将a[lo..hi]复制到aux[lo..hi]
        {
            aux[k] = a[k];
        }
        for (int k = lo; k <= hi; k++)//归并回到a[lo..hi]
        {
            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++];
            }
        }
    }
}

该方法先将所有元素复制到aux[ ]中，然后再归并回a[ ]中。方法在归并时（第二个for循环）进行了4个条件判断：

左半边用尽（取右半边元素）
右半边用尽（取左半边元素）
右半边的当前元素小于左半边的当前元素（取右半边的元素）
右半边的当前元素大于等于左半边的当前元素（取左半边的元素）

# 自顶向下的归并排序

# 算法实现

public class Merge {
    private static Comparable[] aux; //归并所需的辅助数组

    public static void sort(Comparable[] a) {
        aux = new Comparable[a.length];  //一次性分配空间
        sort(a, 0, a.length - 1);
    }

    private static void sort(Comparable[] a, int lo, int hi) {
        //将数组a[lo..hi]排序
        if (hi <= lo) return;
        int mid = lo + (hi - lo) / 2;
        sort(a, lo, mid); //将左半边排序
        sort(a, mid + 1, hi); //将右半边排序
        merge(a, lo, mid, hi);     //归并结果
    }
}

自顶向下的归并排序实际上是对于一个数组先进行拆分，拆分到最小之后进行合并。

自顶向下的归并排序适合对归并排序效率进行分析。归并排序所需的时间和NlgN成正比。可以用归并排序处理数百万甚至更大规模的数组，这是插入排序或者选择排序做不到的。归并排序的主要缺点是辅助数组所使用的额外空间和N的大小成正比。

# 自底向上的归并排序

自底向上归并就是先归并那些微型数组，然后再成对归并得到的子数组，如此我们将整个数组归并在一起。
实现的方法，首先我们两两归并（把每个元素想象成一个大小为1的数组），然后是四四归并，然后是八八归并，一直这样下去。每一轮归并中最后一次归并的第二个子数组可能比第一个子数组要小，但是这不影响merge() 方法。

public class MergeBU {
    private static Comparable[] aux;  //归并所需的辅助数组

    public static void sort(Comparable[] a) {
        //进行lgN次两两归并
        int N = a.length;
        aux = new Comparable[N];
        for (int sz = 1; sz < N; sz = sz + sz)  //sz子数组大小
            for (int lo = 0; lo < N - sz; lo += sz + sz)  //lo 子数组索引
                merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1));
    }
}

自底向上的归并排序比较适合用链表进行排序，这样每次只需要重新组织链表链接就能将链表重新排序。

# 复杂度

归并排序在最坏情况下的比较次数和任意基于比较的排序算法所需的最少比较次数都是~NlgN。
实际上，我们可以严格地认为仅仅只需要lgN!此比较的算法才是最优的排序算法，只不过对于很大的N这种算法的差异不明显。
但实际上，归并排序的空间复杂度显然不是最优的。