Benjamin Lowry Benjamin Lowry - 1 month ago 8
Java Question

MergeSort IllegalArgumentException

So I'm learning about MergeSort right now to solve a problem on Project Euler.

I am trying to sort a list 5163 names alphabetically. I did some research and found that MergeSort would be a fairly efficient way of doing so.

So I coded up an implementation based off of this link.

Below are my

mergeSort
and
merge
methods.

public static List<String> mergeSort(List<String> list){

if (list.size() == 1){ //if fully divided
return list;
}

List<String> leftSide = list.subList(0, list.size()/2);
List<String> rightSide = list.subList(list.size()/2 + 1, list.size());

leftSide = mergeSort(leftSide);
rightSide = mergeSort(rightSide);

return merge(leftSide, rightSide);

}

public static List<String> merge(List<String> listA, List<String> listB){

List<String> listC = new LinkedList<String>();

while (!listA.isEmpty() & !listB.isEmpty()){ //while both have elements
if (listA.get(0).compareTo(listB.get(0)) > 1){ //if stringA is greater than stringB
listC.add(listA.get(0));
listA.remove(0);
} else { //if stringB is greater than stringA
listC.add(listB.get(0));
listB.remove(0);
}
}

while (!listA.isEmpty()){ //while listA has elements
listC.add(listA.get(0));
listA.remove(0);
}

while (!listB.isEmpty()){ //while listB has elements
listC.add(listB.get(0));
listB.remove(0);
}

return listC;

}


The problem is that when I try and use the
mergeSort
method with my list of names, it gives me the following error:


Exception in thread "main" java.lang.IllegalArgumentException: fromIndex(1) > toIndex(0)


Which is pointing at this line:

List<String> rightSide = list.subList(list.size()/2 + 1, list.size());


I don't really understand why it is happening. It seems to me that I have used the exact same method as shown in the tutorial.

Also, from what I understand, this error is telling me that the size of my list is zero. This would be the only way in which
list.size()/2 + 1
could equal one and
list.size()
could equal zero. However, I don't see why my list could be zero. Because it is going to be divided until the size is one, and then it will be returned.

The only way I could see it equalling zero was if it was zero to begin with, but I have confirmed that my
list.size()
is 5163 to start with.

Could someone help me point out what I am doing wrong? I am sure it is something really simple, but since I have just started learning this, I am not sure what it is.

EDIT:

I check the list's size here:

System.out.println(namesArray.size()); //prints "5163"
namesArray = mergeSort(namesArray);


So how could my list ever have a size of zero?

Answer

The only way I could see it equalling zero was if it was zero to begin with, but I have confirmed that my list.size() is 5163 to start with.

There is a second way. Consider what happens deep into your recursion when on entry to mergeSort the input sublist contains two elements.

List<String> leftSide = list.subList(0, list.size()/2);

The above becomes list.sublist(0,1). Since the ending index is exclusive, the sublist contains one element. Then:

List<String> rightSide = list.subList(list.size()/2 + 1, list.size());

This becomes list.sublist(2,2). Again, since the ending index is exclusive, this creates a list of length zero, or an emtpy list. Now when you reach the recursive calls

leftSide = mergeSort(leftSide);
rightSide = mergeSort(rightSide);

the left side recursion works but the right side recursion passes a zero-length list. At the top of mergeSort you have

if (list.size() == 1){ //if fully divided
    return list;
}

which checks for the terminating condition of list size 1, but does not stop the code from attempting to process an empty zero-length list. This is what causes your exception immediately after this point.

If you changed the test to if (list.size() <= 1) you'd have prevented the exception, but would still have a problem since some of the elements would not have been sorted due to the ending index problem.

The correct solution is to change one line:

List<String> rightSide = list.subList(list.size()/2 + 1, list.size());
                                                    ^^^
        Remove this----------------------------------^