递归合并仅分为阵列的一半

Question

我正在尝试实现递归合并量算法以对简单的整数排序，但是我在数组的下半部分数获得了索引的怪异值。上半场似乎排序良好，鉴于其递归实施，这令人困惑。随机整数的数组以我的主要方法初始化。

public class MergeSort {
public static int Rounds = 1;
public static void MergeSort(Comparable[] ToSort, Comparable[] temp, int first, int last) {
    if(first < last) {
        int mid = (first + last) / 2;
        //Test Block
        System.out.print("For Round " + Rounds + ":n");
        System.out.print("first = " + first + "   mid = " + mid + "   last = " + last + "n");
        Rounds++;
        System.out.print("Array in Round " + (Rounds - 1) + " = {");
        for(int i = 0; i <= ToSort.length - 1; i++) {
            System.out.print(ToSort[i]);
            if(i < ToSort.length - 1)
                System.out.print(", ");
            else {
                System.out.print("}nn");
            }
        }
        MergeSort(ToSort, temp, first, mid);
        MergeSort(ToSort, temp, mid + 1, last);
        Merge(ToSort, temp, first, mid + 1, last);
    }
}
public static void Merge(Comparable[] ToSort, Comparable[] temp, int first, int mid, int last) {
    int beginHalf1 = first;
    int endHalf1 = mid - 1;
    int beginHalf2 = mid;
    int endHalf2 = last;
    int index = first;
    int Elements = (last - first) + 1;
    while(beginHalf1 <= endHalf1 && beginHalf2 <= endHalf2) {
        if(ToSort[beginHalf1].compareTo(ToSort[beginHalf2]) < 0) temp[index++] = ToSort[beginHalf1++];
        else temp[index++] = ToSort[beginHalf2++];
    }
    while(beginHalf1 <= endHalf1) temp[index++] = ToSort[beginHalf1++];
    while(beginHalf2 <= endHalf2) temp[index++] = ToSort[beginHalf2++];
    for(int i = 0; i < Elements; i++, last--) ToSort[last] = temp[last];
}

}

这会产生以下输出：

unsorted array = {15、9、12、19、49、43、57、70、78、87}对于第1轮：首先= 0 mid = 4 last = 9第1轮中的数组= {15、9、9、12、19、49、43、57、70、78、87}

第2轮：首先= 0 mid = 2 last = 4第2轮中的数组= {15、9、12、19、49、43、57、70、78、87}

第3轮：首先= 0 mid = 1 last = 2第3轮中的数组= {15、9、12、19、49、43、57、70、78、87}

第4轮：首先= 0 mid = 0 last = 1第4轮中的数组= {15、9、9、12、19、49、43、57、70、78、87}

第5轮：首先= 3 mid = 3 last = 4第5轮中的数组

第6轮：首先= 5 mid = 7 last = 9第6轮中的数组= {9、12、15、19、49、43、57、70、78、87}

第7轮：首先= 5 mid = 6 last = 7第7轮中的数组= {9、12、15、19、49、43、57、70、78、87}

第8轮：第一个= 5 mid = 5 last = 6第8轮中的阵列= {9、12、15、19、49、43、57、70、78、87}

第9轮：首先= 8中= 8 last = 9第9轮中的阵列= {9、12、15、19、49、43、57、70、78、87}

Answer 1

您的实现没有任何错误。如果您在应用MergeSort方法后打印数组，则进行排序：

Comparable[] a = new Comparable[]{15, 9, 12, 19, 49, 43, 57, 70, 78, 87};
Comparable[] b = new Comparable[a.length];
MergeSort.MergeSort(a, b, 0, a.length - 1);
for (int i = 0; i <= a.length - 1; i++) {
    System.out.print(a[i]);
    if (i < a.length - 1)
        System.out.print(", ");
    else {
        System.out.print("}nn");
    }
}

将打印9, 12, 15, 19, 43, 49, 57, 70, 78, 87}