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

需要减少将a复制到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;

    if (a.length <= 4)
    {
        Insertion.sort(a);
    }
    else
    {
        sort(a, lo, mid);
        sort(a, mid + 1, hi);

        if (a[mid].compareTo(a[mid + 1]) > 0)
        {
            merge(a, aux, lo, mid, hi);
            merge(aux, a, lo, mid, hi);
        }
    }
}

public static void merge(Comparable[] a, Comparable[] aux, 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++)
    {
        if (i > mid) {
            aux[k] = a[j++];
        } else if (j > hi) {
            aux[k] = a[i++];
        } else if (less(a[j], a[i])) {
            aux[k] = a[j++];
        } else {
            aux[k] = a[i++];
        }
    }

    //StdOut.println("lo: " + lo + ", hi: " + hi);
}