归并排序

基本思路

将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。

最基本的算法——归并操作

归并：一个集合前半部分有序，后半部分也有序，现在通过归并的手段让整体有序
基本算法：依次从两个集合中取数据，谁小谁放前面

private static void mergeArray1(Comparable[] a, int start, int middle, int end) {
    Comparable[] temp = new Comparable[end - start + 1];
    int i = start;
    int j = middle + 1;
    int k = 0;
    while ((i <= middle) && (j <= end)) {
        if (less(a[i], a[j])) {
            temp[k++] = a[i++];
        } else {
            temp[k++] = a[j++];
        }
    }
    while (i <= middle) {
        temp[k++] = a[i++];
    }
    while (j <= end) {
        temp[k++] = a[j++];
    }
    System.arraycopy(temp, 0, a, start, end - start + 1);
}

我们可以看到归并操作，需要创建一个临时集合来存放有序数据，最后再把数据copy回原集合。归并操作在归并排序中是需要递归调用的，频繁的new 集合不合理。

原地归并的方案

我们希望能够尽可能的原地归并数据，当然不可能完全实现。一个可行的方案是：排序前建一个和原数组大小相等的辅助数组，在每一次merge操作时，将对应的数据先copy过来，然后将数据从辅助数组排序到输入数组。

    private static void mergeArray2(Comparable[] a, int start, int middle,
            int end, Comparable[] temp) {
        int i = start;
        int j = middle + 1;
        int k = start;
        System.arraycopy(a, start, temp, start, end - start + 1);
        while ((i <= middle) && (j <= end)) {
            if (less(temp[i], temp[j])) {
                a[k++] = temp[i++];
            } else {
                a[k++] = temp[j++];
            }
        }
        while (i <= middle) {
            a[k++] = temp[i++];
        }
        while (j <= end) {
            a[k++] = temp[j++];
        }
    }

我们看到mergeArray2和mergeArray1最大的区别就是：
mergeArray1归并动作在辅助数组中完成，辅助数组完成归并后，再arrayCopy回原数组。
而直接mergeArray2在原数组中归并。也就是所谓的原地归并。

自顶向下的归并排序（递归）

上面我们已经有了基本的归并算法，那么归并排序也就很清晰了：
1.找到数组的middle
2.递归的对上半部分排序，递归的对下半部分排序
3.归并操作

几个注意的点：

1. 当递归到一定程度，数组元素已经比较少的时候，可以使用插入或者选择排序进行排序
2. 由于上下两部分都是有序数组，当恰好a[middle]<a[middle+1]时，就可以认为已经是有序的。

    public static void merge_sort(Comparable[] a) {
        Comparable[] temp = new Comparable[a.length];
        mergesort(a, 0, a.length - 1, temp);
    }

    private static void mergesort(Comparable[] a, int start, int end,
            Comparable[] temp) {
        if (end - start + 1 < 15) { //小于15的数据，可以采用插入或者选择排序
            select_sort(a, start, end);
        } else {
            int middle = (start + end) / 2;
            if (start < end) {
                mergesort(a, start, middle, temp);
                mergesort(a, middle + 1, end, temp);
                if (!less(a[middle], a[middle + 1])) { //如果a[middle]< a[middle + 1],我们认为已经有序
                    mergearray(a, start, middle, end, temp);
                }
            }
        }
    }

自底向上的归并排序（非递归，适合链表）

既然有递归的方案，那反过来一定有非递归的方案。
方案：归并微型数组，然后成对归并得到的子数组，直到将整个数组归并到一起。

1. mergeArray(0,0,1) mergeArray(2,2,3)—— mergeArray(0,1,3)
2. mergeArray(0,1,3) mergeArray(4,5,7)—— mergeArray(0,3,7)
3. mergeArray(0,3,7) mergeArray(8,11,15)
4. 如此反复，直到合并为一个大小为N的数组

    private static void mergeBU_sort(Comparable[] a) {
        Comparable[] temp = new Comparable[a.length];
        int N = a.length;
        for (int sz = 1; sz < N; sz = sz + sz) { // sz为每次归并的数组长度，从1开始，一直到N/2
            for (int start = 0; start < N - sz; start += sz + sz) { // 对每一个数组进行mergearray操作
                int middle = start + sz - 1;
                int end = start + sz - 1 + sz;
                mergearray(a, start, middle,
                        Math.min(end, N - 1), temp);
            }
        }
    }