java - 无法找出我的通用mergeSort，IndexOutBoundException错误

这是我到目前为止所拥有的...

public class SortUtil {
// Add any instance variables here //
SortUtilComparator comparatorObj = new SortUtilComparator();

public SortUtil() {
}

/**
 * This method performs a mergesort on the generic ArrayList given as input.
 *
 * @param arrayMerge - the generic ArrayList to sort
 * @param comparator - comparator to compare the elements
 */
public static <T> void mergesort(ArrayList<T> arrayMerge, Comparator<? super T> comparator) {
    ArrayList<T> tempArray = new ArrayList<T>();
    mergesortRecursive(arrayMerge, tempArray, 0, arrayMerge.size()-1, comparator);
}

/**
 *
 * @param arrayMerge -  ArrayList to sort
 * @param tempArrayList - temporary ArrayList used to merge
 * @param left - the first index of the range to sort
 * @param right - last index of the array range to sort
 * @param comparator - comparator to compare the elements
 */
public static <T> void  mergesortRecursive(ArrayList<T> arrayMerge, ArrayList<T> tempArrayList, int left, int right, Comparator<? super T> comparator ) {
    if (left == right){
        return;
    }

    if(left < right && (right-left) >= 1){
        int mid = (left + right) / 2;

        mergesortRecursive(arrayMerge, tempArrayList, left, mid, comparator);
        mergesortRecursive(arrayMerge, tempArrayList, mid+1, right, comparator);

        // Sorts the first and second half of the ArrayList
        merge(arrayMerge, tempArrayList, left, mid, right, comparator); // and merges/sorts the array in the merge() method
    }
}

/**
 * Sorts the ArrayList using merge sort algorithm.
 *
 * @param arrayValues - the ArrayList needing to be sorted / merged
 * @param tempArray - temporary ArrayList used for merging
 * @param start - the first index of the range to sort
 * @param mid - the first index of the range to sort
 * @param end - last index of the array range to sort
 * @param comparator - comparator to compare the elements
 */
public static <T> void merge(ArrayList<T> arrayValues, ArrayList<T> tempArrayList, int start, int mid, int end, Comparator<? super T> comparator ){

    // Next element to consider in the first half of arrayValues<T>
    int startValueIndex = start;

    // Next element to consider in the second half of arrayValues<T>
    int midValueIndex = mid + 1;

    // As long as neither start or mid pass the end, move the smaller element into tempArrayValues<T>
    while(startValueIndex <= mid && midValueIndex <= end)
    {

        if(comparator.compare(arrayValues.get(startValueIndex), arrayValues.get(midValueIndex)) <= 0){
            tempArrayList.add(arrayValues.get(startValueIndex)); // adds smaller element of the left array on farthest left index into temporary array
            startValueIndex++; // increments this index so it can check
        }
        else{
            tempArrayList.add(arrayValues.get(midValueIndex)); // adds smaller element of the right array on farthest left index into temporary array
            midValueIndex++;
        }
    }

    // Only one of the while loops below will execute if there's still remaining elements.

    // Take remaining elements of the first half ArrayList
    while(startValueIndex <= mid){
        tempArrayList.add(arrayValues.get(startValueIndex));
        startValueIndex++;
    }

    // Take remaining elements of the second half ArrayList
    while(midValueIndex <= end){
        tempArrayList.add(arrayValues.get(midValueIndex));
        midValueIndex++;
    }

    int i = 0;
    int j = start;
    while(i < tempArrayList.size()){
        arrayValues.set(j, tempArrayList.get(i++));
        j++;
    }
}

我得到的错误是：

java.lang.IndexOutOfBoundsException: Index: 5, Size: 5
at java.util.ArrayList.rangeCheck(ArrayList.java:653)
at java.util.ArrayList.set(ArrayList.java:444)
at assignment05.SortUtil.merge(SortUtil.java:149)
at assignment05.SortUtil.mergesortRecursive(SortUtil.java:94)
at assignment05.SortUtil.mergesortRecursive(SortUtil.java:90)
at assignment05.SortUtil.mergesortRecursive(SortUtil.java:91)
at assignment05.SortUtil.mergesort(SortUtil.java:71)
at assignment05.SortUtilTests.mergeSort_Test1(SortUtilTests.java:49)

我一直在尝试找出答案，更改代码的排序方式，但我只是无法弄清楚它是如何获得异常的。我已经进行了调试，并进行了一些sysout打印测试，但是，我现在不知道该怎么做才能使其正常工作。

编辑：这就是我试图对其进行测试的方式：

@Test
public void mergeSort_Test1() {
    ArrayList<Integer> values = new ArrayList<Integer>();
    values.add(1);
    values.add(5);
    values.add(7);
    values.add(2);
    values.add(10);

    ArrayList<Integer> expectedValuesArrayList = new ArrayList<Integer>();
    expectedValuesArrayList.add(1);
    expectedValuesArrayList.add(2);
    expectedValuesArrayList.add(5);
    expectedValuesArrayList.add(7);
    expectedValuesArrayList.add(10);

    SortUtil.mergesort(values, comparatorObj);
    Assert.assertEquals(expectedValuesArrayList, values);
}

我的SortUtilComparator是：

public class SortUtilComparator implements Comparator<Integer> {

public int compare(Integer o1, Integer o2) {
    return o1.compareTo(o2);
}

最佳答案

您为ArrayList<T> tempArrayList函数的每次调用都向merge添加了越来越多的元素。因此，您终于到了tempArrayList大于原始数组的那一刻，因此将tempArrayList辅助到arrayValues.set(j, tempArrayList.get(i++));的原始数组时，您会得到IndexOutOfBoundsException。

您必须在每次merge调用时使用新的临时数组，或者在tempArrayList.clear()开头将其清除。