题目要求

它要求将一个长度为N的数据，分为N/M个子块。每个块先用选择排序进行排序，再依次归并各个块。要求使用的额外空间为max(M, N/M)。

这道题的难点在merge方法，对块1我用@1表示，对块2我用@2表示。 依次对比@1和@2的数据，将@2中小于@1的数据，将其暂存到aux中，当到达数组末尾或@2不小于@1时，将其插入到数组a中。

// 原地归并
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;
    int ax = 0;
    // 由于lo..mid mid+1..hi都是有序的，
    // 所以当i > mid或j > hi时，跳出循环
    while (i <= mid && j <= hi)
    {
        if (less(a[j], a[i])) {
            aux[ax++] = a[j++];
            if (j > hi) {
                moveEnd(a, i, hi - ax, aux, ax);
                i = i + ax;
                ax = 0;
            }
        } else {
            if (ax > 0) {
                moveEnd(a, i, j - ax - 1, aux, ax);
                i = i + ax;
                ax = 0;
            } else {
                i++;
            }
        }
    }
    //StdOut.println();
}

moveEnd方法，用于在指定索引处插入数据, 它是merge方法的辅助方法。

/**
 * 将[beginPos..endPos]之间的数据后移指定个数，并在此区间上写入数据
 * @param a 待移动的数组
 * @param beginPos 开始坐标
 * @param endPos 结束坐标
 * @param vals 要插入的元素数组
 * @param count 要插入的数量，同时也是后移的数量
 */
private static void moveEnd(Comparable[] a, int beginPos, int endPos, Comparable[] vals, int count)
{
    for (int i = endPos + count; i >= beginPos + count; i--)
    {
        a[i] = a[i - count];
    }
    int c = beginPos;
    for (int i = 0; i < count; i++)
    {
        a[c++] = vals[i];
    }
}

sort方法：

public static void sort(Comparable[] a)
{
    // 假设n=8
    int N = a.length;
    int M = 4;
    int count = N / M; // 分成的块数
    int len = Math.max(M, N/M);
    StdOut.println("aux数组长度为：" + len);
    aux = new Comparable[len];

    // 分块排序
    for (int i = 0; i < count; i++)
    {
        int x = 0;
        for (int j = i * M; j < (i + 1) * M; j++)
        {
            aux[x++] = a[j];
        }
        Selection.sort(aux);
        // 将排序后的aux复制回a
        x = 0;
        for (int j = i * M; j < (i + 1) * M; j++)
        {
            a[j] = aux[x++];
        }
    }

    for (int i = 1; i < count; i++)
    {
        int lo = 0;
        int mid = i * M - 1;
        int hi = Math.min(a.length, (i + 1) * M - 1);

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

        merge(a, lo, mid, hi);
        StdOut.println();
    }
}

执行效果：16个元素

T X R V L A F D Q N Y W S P O I 
aux数组长度为：4
lo: 0, mid: 3, hi: 7

lo: 0, mid: 7, hi: 11

lo: 0, mid: 11, hi: 15

A D F I L N O P Q R S T V X W Y