2.2.11 要求改进2.2.2归并排序，加快小数组排序，检测数组已经有序及通过在递归中交换参数避免数组复制。

最开始的时候，这个交换参数，怎么也想不明白，算法题就是这样，经常是因为理解错误题目造成的问题。最开始我以为是交换aux、a的参数。最后苦思良久，才恍然大悟是不使用aux，而是直接交换a的数据。

代码如下：

public static void sort(Comparable[] a)
{
    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;

    // 处理小数组排序问题
    if (a.length < 15)
    {
        Insertion.sort(a);
    }
    else
    {
        sort(a, lo, mid);
        sort(a, mid + 1, hi);
        // 已经有序
        if (a[mid].compareTo(a[mid + 1]) > 0)
        {
            merge(a, lo, mid, hi);
        }
    }
}

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;

        String s = "";
        // 归并回到a[lo..hi]
        for (int k = lo; k <= hi; k++)
        {
            if (i > mid) {
                j++;
            } else if (j > hi) {
                i++;
            } else if (less(a[j], a[i])) {
                exch(a, i, j);
            } else {
                exch(a, ++i, j);
            }
        }
    }