Java Merge sort recieving error message

Question

I'm very new to java and I'm doing an assignment where were required to use merge sort but I continue to get errors. We're using ArrayList and its causing me to make a lot of mistakes. I posted the code below as well as the error I continue to get, can anyone help me figure out why this is happening?

import java.util.ArrayList;
import java.util.UUID;

public class mSort {

public static ArrayList<String> randomList() {
    ArrayList<String> a = new ArrayList<String>();

    for(int i = 0; i < 10; i++) {
        a.add(i, UUID.randomUUID().toString());
    }

    return a;
}

public void sort(ArrayList<String> list) {
    sortArray(0, list.size(), list);
}

private void sortArray(int low, int high, ArrayList<String> list) {
    if ((high - low) >= 1) {
        int middle1 = ( low + high ) / 2;
        int middle2 = middle1 + 1;

        sortArray(low, middle1, list);
        sortArray(middle2, high, list);
        merge(low, middle1, middle2, high, list);
    }
}

private void merge(int left, int middle1, int middle2, int right, ArrayList<String> list) {
    int leftIndex = left;
    int rightIndex = middle2;
    int combinedIndex = left;
    ArrayList<String> combined = new ArrayList<String>();
    ArrayList<String> data = list;

    while (leftIndex <= middle1 && rightIndex <= right) {
        if (data.get(leftIndex).compareTo(data.get(rightIndex)) < 0) {
            combined.add(combinedIndex, data.get(leftIndex));
            combinedIndex++;
            leftIndex++;
        }
        else {
            combined.add(combinedIndex, data.get(rightIndex));
            combinedIndex++;
            rightIndex++;
        }
    }

   if (leftIndex == middle2) {
       while (rightIndex <= right) {
           combined.add(combinedIndex, data.get(rightIndex));
           combinedIndex++;
           rightIndex++;
       }
   }
   else {
       while ( leftIndex <= middle1 ) {
           combined.add(combinedIndex, data.get(leftIndex));
           combinedIndex++;
           leftIndex++;
       }
   }
   for (int i = left; i <= right; i++ ) {
       list.set(i, combined.get(i));
       //System.out.println(list.get(i));
   }
}

public static void main(String[] args) {
    ArrayList<String> list = randomList();
    mSort sorted = new mSort();
    sorted.sort(list);

    for ( int i = 0; i < list.size(); i++ ) {
        System.out.println(list.get(i));
    }
}

}

here's the stack trace for the error:

Exception in thread "main" java.lang.IndexOutOfBoundsException: Index: 3, Size: 0
at java.util.ArrayList.rangeCheckForAdd(Unknown Source)
at java.util.ArrayList.add(Unknown Source)
at mSort.merge(mSort.java:40)
at mSort.sortArray(mSort.java:27)
at mSort.sortArray(mSort.java:25)
at mSort.sortArray(mSort.java:26)
at mSort.sortArray(mSort.java:25)
at mSort.sort(mSort.java:17)
at mSort.main(mSort.java:74)

Answer 1

There are a couple of problems.

1. sortArray(0, list.size(), list); needs to be sortArray(0, list.size() - 1, list); because indexes go from 0 to size - 1;

2. The lines combined.add(combinedIndex, data.get(rightIndex)); in merge.
   You can't add to an index that is out side this range 0 <= index <= size. When you do it should throw an IndexOutOfBoundsException according to the documentation. (Which it does). This is the reason you see the exception. The size of the combined ArrayList is 0 and you are trying to insert at index 3.
   You can change all of these lines to be just combined.add(data.get(...)); (remove the combinedIndex). The combinedIndex variable should not be needed because the array should already be partially sorted so appending should keep it sorted.

3. The block below at the end of merge alls needs to be changes so you don't get outside of the size() of the combined array list. Shown below.

Before

for (int i = left; i <= right; i++ ) {
    list.set(i, combined.get(i));
}

After

for (int i = left; i <= right; i++ ) {
    list.set(i, combined.get(i - left));
}