java - 实现非递归（自下而上）MergeSort 算法

Question

我被分配执行以下算法：

 

阅读算法本身让我有点困惑，我尝试遵循算法，但是由于我无法完全理解它，我的代码不起作用。任何人都可以看看我的代码（这是我不明白要解决什么问题的一点）：

public static void mergeSortNonRec(Comparable[] a) {
    Comparable[] a1 = new Comparable[a.length];
    Comparable[] b = new Comparable[a.length];

    for (int i = 1; i < a.length; i *= 2) {
        for (int j = 0; j < a.length; j += 2 * i) {
            merge(a1, j, (Integer.min(j + i, a.length) - 1), a1, j + i, (Integer.min(j + 2 * i, a.length) - 1), b, 0);
        }
    }

    for (int i = 0; i < a.length; i++) {
        a[i] = a1[i];
    }
}

这是我用递归 mergeSort 测试过的辅助方法，我知道它有效：

private static void merge(Comparable[] a1, int left1, int right1, Comparable[] a2, int left2, int right2, Comparable[] a, int left) {
    int i = left1;
    int j = left2;
    int k = left;

    while (i <= right1 && j <= left2) {
        int comp = a1[i].compareTo(a2[j]);
        if (comp <= 0) {
            a[k++] = a1[i++];
        } else {
            a[k++] = a2[j++];
        }
    }
    while (i <= right1) {
        a[k++] = a1[i++];
    }
    while (j <= right2) {
        a[k++] = a2[j++];
    }
}