Why does this Java code trigger a ConcurrentModificationException?

In the first line of the loop I get the error, but I don’t see why. From what I read this should happen only if I’m iterating over a collection and trying to modify it at the same time, but this is not the case.

In the code, list is of type ArrayList<Product>.

void mergeSort() { 
    mergeSort(0, list.size() - 1); //128
}

private void mergeSort(int p, int r) {
    if (p < r) {
        int q = (p + r) / 2;
        mergeSort(p, q); //133
        mergeSort(q + 1, r);
        merge(p, q, r); //135
    }
}

private void merge(int p, int q, int r) {
    List<Product> left = list.subList(p, q);
    left.add(Product.PLUS_INFINITE);
    List<Product> right = list.subList(q + 1, r);
    right.add(Product.PLUS_INFINITE);
    int i = 0;
    int j = 0;
    for (int k = p; k <= r; ++p) {
        Product x = left.get(i).compareTo(right.get(j)) <= 0 ? left.get(i++) : right.get(j++); //147
        list.set(k, x);
    }
}

This is the stacktrace:

Exception in thread "main" java.util.ConcurrentModificationException
    at java.base/java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1415)
    at java.base/java.util.ArrayList$SubList.get(ArrayList.java:1150)
    at ProductList$ProductSort.merge(MainClass.java:147)
    at ProductList$ProductSort.mergeSort(MainClass.java:135)
    at ProductList$ProductSort.mergeSort(MainClass.java:133)
    at ProductList$ProductSort.mergeSort(MainClass.java:128)
    at ProductList.sort(MainClass.java:95)
    at MainClass.main(MainClass.java:187)

Answer

subList does not create a new list that has the same elements as the original list in the specified range. Rather, it creates a “view” (docs):

Returns a view of the portion of this list […]. The returned list is backed by this list, so non-structural changes in the returned list are reflected in this list, and vice-versa.

Also note:

The semantics of the list returned by this method become undefined if the backing list (i.e., this list) is structurally modified in any way other than via the returned list.

This is exactly what you are doing in merge. You are creating sublists left. Then modifying left structurally with add. So far so good. But then you created another sublist right and modifies it as well. This makes “the semantics of left to become undefined”. And this causes the next call to get to throw an exception.

Minimal reproducible example:

ArrayList<String> list = new ArrayList<>(List.of("1", "2", "3", "4"));
List<String> left = list.subList(0, 2);
List<String> right = list.subList(2, 4);
right.add("5");
left.get(0);

Sublists are a bit like iterators in this regard (you can only remove via the iterator, if you remove via the original list, CME might be thrown).

One simple way to fix this is to create copies of the sublists so that they are no longer “views”, but are actually independent lists:

List<Product> left = new ArrayList<>(list.subList(p,q));
List<Product> right = new ArrayList<>(list.subList(q+1,r));