归并排序

要将一个数组排序，可以先（递归地）将它分成两半分别排序，然后将结果归并起来。这就是归并排序，而归并的意思即将两个有序的数组归并成一个更大的有序数组

熟记于心

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

    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    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数组
            aux[k] = a[k];
        }

        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[i], aux[j])) a[k] = aux[i++];
            else a[k] = aux[j++];
        }
    }

    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) {
        //递归终止条件：下限超过上限，意味着没有元素需要排序，该base case直接return
        if (lo >= hi) return; 
        int mid = (lo + hi) >>> 1;
        sort(a, lo, mid);   //将左半边排序
        sort(a, mid + 1, hi);   //将右半边排序
        merge(a, lo, mid, hi);  //归并结果
    }
}

Tips:

• 能够保证将任意长度为N的数组排序所需时间和NlogN成正比，主要缺点是需要额外空间
• 如果不需要额外空间，那么代码非常复杂
• merge()方法中，先将所有元素复制到aux[]中，然后再归并回a[]中，方法在归并时(第二个for循环)进行了4个条件判断:左半边用尽（取右半边的元素）、右半边用尽（取左半边的元素）、以及取较小元素的两个判断条件