Cannot figure out my generic mergeSort, IndexOutBoundException error

Question

This is what I have so far...

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++;
    }
}

And the error that I get is:

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)

I've been trying to figure it out, changing how the code will sort a bit, but I just can't figure out how it's getting the exception. I've followed debugging and did some sysout print testing but, I just can't figure out what I can do at this point to have it working.

EDIT: This is how I'm trying to test it:

@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);
}

My SortUtilComparator is:

public class SortUtilComparator implements Comparator<Integer> {

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

Answer 1

You are adding more and more elements to you ArrayList<T> tempArrayList for each call of merge function. Because of that you are finally coming to the moment when your tempArrayList is bigger then your original array so when assiging tempArrayList to original array at arrayValues.set(j, tempArrayList.get(i++)); you are getting IndexOutOfBoundsException.

You have to use new temp array at each call of merge or clear it at beginning of it with tempArrayList.clear().