Java: Unexpected runtime error in a recursive function

Question

I'm trying to write my own version of MergeSort and wrote the following class:

import java.util.List;
import java.util.LinkedList;
import java.lang.Comparable;

public class Sort<E extends Comparable<E>> {
  private List<E> list;

  public void setList(List<E> inList) {list = inList;}
  public List<E> getList() {return list;}

  public List<E> mergeSortRec(List<E> inList) {
    if (inList == null) return null;
    if (inList.size() < 2) return inList;
    int mdpt = inList.size()/2;
    List<E> left = inList.subList(0,mdpt);
    List<E> right = inList.subList(mdpt,inList.size());
    left = mergeSortRec(left);
    right = mergeSortRec(right);
    List<E> out = new LinkedList<E>();
    while (left.size()>0 && right.size()>0) {
      if (left.get(0).compareTo(right.get(0)) < 0) {
        out.add(left.remove(0));
      } else {
        out.add(right.remove(0));
      }
    }
    if (left.size()==0) {
      while (right.size()>0) {
        out.add(right.remove(0));
      }
    } else {
      while (left.size()>0) {
        out.add(left.remove(0));
      }
    }
    return out;
  }
  public void mergeSort() {list = mergeSortRec(list);}
}

However, the following main class,

import java.util.LinkedList;

public class Main {
  public static void main(String[] args) {
    System.out.println("Input list:");
    LinkedList<Integer> lst = new LinkedList<Integer>();
    lst.add(3);
    lst.add(1);
    lst.add(5);
    Sort<Integer> s = new Sort<Integer>();
    s.setList(lst);
    s.mergeSort();
  }
}

causes the following error,

Exception in thread "main" java.util.ConcurrentModificationException
    at java.util.SubList.checkForComodification(AbstractList.java:769)
    at java.util.SubList.size(AbstractList.java:645)
    at Sort.mergeSortRec(Sort.java:69)
    at Sort.mergeSortRec(Sort.java:59)
    at Sort.mergeSort(Sort.java:79)
    at Main.main(Main.java:12)

After inserting print lines I see that the issue comes from the call to left.size() in if (left.size()==0) {, and I believe it is occurring in the "zeroth level" of the recursive call, that is to say, it's happening when inList is the whole original list, and left is 3 and right is 1,5. I can't understand why a method call to left would cause an error. I only dimly grasp how there could be some concurrency issue but I have pretty much no experience with that, and I would think that it would be obviated by the fact that left is the return value of a function and therefore shouldn't be referenced by multiple variables--if that's anything to do with the issue.

Rann Lifshitz · Accepted Answer · 2018-06-22T01:53:45.230

The problem here is due to the removal of an item from a list which is being iterated on:

 while (left.size()>0 && right.size()>0) { // iteration on left/right lists
      if (left.get(0).compareTo(right.get(0)) < 0) {
        out.add(left.remove(0)); // modification of the left list
      } else {
        out.add(right.remove(0)); // modification of the right list
      }
 }

Removing items during the while iteration violates the contract of the list object and results in your exception - ConcurrentModificationException.

There are multiple ways to handle this issue -

Using a copy of the lists which will be modified, while iterating on the original lists. In this case, you can use a size counter instead of calling the lists size method.
Using an Iterator and the Iterator's dedicated remove() method.
With Java 8 you can use the Collection.removeIf method.

References:

This actually explains a lot, not just my issue, but also why I've seen other people implement MergeSort using position trackers--that would have avoided this issue all together. — Addem, Jun 22 '18 at 01:56

Java: Unexpected runtime error in a recursive function

1 Answers1