0

I am trying to implement merge sort in java, but this causes a ConcurrentModificationException in the line while(ai<la.size()&&bi<lb.size()){. I have seen a lot of answers on Stack about this but they all relate to removing items from a list, but I am not doing that. What is causing this exception, and how can I fix this?

public static <Elem extends Comparable<Elem>> void mergesort(List<Elem> list) {
    if(list.size()>1){
        int hf = list.size()/2;
        List<Elem> la = list.subList(0, hf-1);
        List<Elem> lb = list.subList(hf, list.size()-1);
        mergesort(la);
        mergesort(lb);
        int ai=0;
        int bi=0;
        int oi=0;
        while(ai<la.size()&&bi<lb.size()){
            if(la.get(ai).compareTo(lb.get(bi))>0){
                list.add(oi, la.get(ai));
                ai++;
            }
            else{
                list.add(oi, lb.get(bi));
                bi++;
            }
            oi++;
        }
        while(ai<la.size()){
            list.add(oi, la.get(ai));
            ai++;
            oi++;
        }
        while(bi<lb.size()){
            list.add(oi, lb.get(bi));
            bi++;
            oi++;
        }
    }
}

But testing this with as mergesort(Arrays.asList(3, 2, 1, 6, 5, 4)) causes the following error:

java.util.ConcurrentModificationException
at java.util.ArrayList$SubList.checkForComodification(ArrayList.java:1231)
at java.util.ArrayList$SubList.size(ArrayList.java:1040)
at week04.MergeSort.mergesort(MergeSort.java:17)
at week04.test.MergeSortTest.testMergesortUnsortedList(MergeSortTest.java:42)

CerebralFart
  • 3,336
  • 5
  • 26
  • 29
  • 1
    What's row 42?? – Idos Jan 09 '17 at 15:59
  • 1
    public static > void mergesort(List list) { List listNew = Collections.synchronizedList(list) , and then do the merge – gaston Jan 09 '17 at 15:59
  • @Idos, line 42 is `MergeSort.mergesort(sequence);`, sequence is initialized as `List sequence = new ArrayList<>(Arrays.asList(3, 2, 1, 5, 4));` – CerebralFart Jan 09 '17 at 16:01
  • @gaston, could you elaborate? – CerebralFart Jan 09 '17 at 16:01
  • 5
    when you take a `subList` it is only valid if you don't use an operation which might modify the underlying list. If you call a method which might modify the list it reports a CME. – Peter Lawrey Jan 09 '17 at 16:03
  • 2
    I suggest changing the method to be `mergesort(List list, int from, int to)` so you don't need to use a subList and you won't have this problem. Note: you cannot safely iterate over a collection as you modify it. – Peter Lawrey Jan 09 '17 at 16:05
  • 1
    Possible duplicate of [Why ConcurrentModificationException in ArrayList?](http://stackoverflow.com/questions/12793199/why-concurrentmodificationexception-in-arraylist) – Andremoniy Jan 09 '17 at 16:22

0 Answers0