IndexOutOfBoundsException implementing Merge sort on a String ArrayList in Java

Question

I am trying to use merge sort on a String Array List, but I am getting the error:

java.lang.IndexOutOfBoundsException: Index: 0, Size: 0

and it is killing me. Can someone please help me out and tell me what am I doing wrong:

ArrayList<String> input = new ArrayList();
public void mergeSort(ArrayList<String> a, int first, int last)
{
      if(first == last)
      {
         return;
      }
      int mid = (first+last)/2;
      mergeSort(a, first, mid);
      mergeSort(a, mid+1, last);
      merge(a, first, mid, last);   
}
   public void merge(ArrayList<String> a, int firstLeft, int lastLeft, int lastRight)
{
      //Create a temporary ArrayList to do the merging
      ArrayList<String> temp = new ArrayList();

      //Merge elements and put them in the temporary arraylist
      int firstRight = lastLeft + 1; //first index of right array
      int indexLeft = firstLeft; //index for left array
      int indexRight = firstRight; //index for right array
      int indexTemp = indexLeft; //index for merged array

      while(indexLeft <= lastLeft && indexRight <= lastRight)
      {
         if((a.get(indexLeft).compareTo(a.get(indexRight)))<0)
         {
            temp.set(indexTemp++,(a.get(indexLeft++)));
         }
         else
         {
            temp.set(indexTemp++,(a.get(indexRight++)));
         }
      }
      while(indexLeft <= lastLeft)
      {
          temp.set(indexTemp++,(a.get(indexLeft++)));
      }
      while(indexRight <= lastRight)
      {
          temp.set(indexTemp++,(a.get(indexRight++)));
      }
      //copy the sorted array back to the original array
      a = temp;
}

Function Call:

ArrayList<String> input = new ArrayList();
mergeSort(input, 0, (input.size()-1));

The ArrayList input has unsorted values;
When I output the size of the input arraylist it gives me 7373.

Answer 1

I did some changes in your code and I think it works:

• methods are not passing any list, those are using input instance list
• temp list is started with input content to avoid IndexOutOfBoundsException

---

public void merge() {
    mergeSort( 0, input.size() - 1);
}


public void mergeSort(int first, int last)
{
      if(first == last)
      {
         return;
      }
      int mid = (first+last)/2;
      mergeSort(first, mid);
      mergeSort(mid+1, last);
      merge(first, mid, last);   
}
public void merge(int firstLeft, int lastLeft, int lastRight)
{
      //Create a temporary ArrayList to do the merging
      ArrayList<String> temp = new ArrayList(input);

      //Merge elements and put them in the temporary arraylist
      int firstRight = lastLeft + 1; //first index of right array
      int indexLeft = firstLeft; //index for left array
      int indexRight = firstRight; //index for right array
      int indexTemp = indexLeft; //index for merged array

      while(indexLeft <= lastLeft && indexRight <= lastRight)
      {
         if((input.get(indexLeft).compareTo(input.get(indexRight)))<0)
         {
            temp.set(indexTemp++,(input.get(indexLeft++)));
         }
         else
         {
            temp.set(indexTemp++,(input.get(indexRight++)));
         }
      }
      while(indexLeft <= lastLeft)
      {
          temp.set(indexTemp++,(input.get(indexLeft++)));
      }
      while(indexRight <= lastRight)
      {
          temp.set(indexTemp++,(input.get(indexRight++)));
      }
      //copy the sorted array back to the original array
      input = temp;
}

now, we could use sorting like this:

MergeSortImp mSort = new MergeSortImp();
mSort... //(some method created to fill input list)
mSort.mergeSort( 0, input.size() - 1);

Answer 2

It happens because you are trying to set an index in the list which does not exist yet - temp.set(indexTemp++,(a.get(indexRight++))); And list api doesn't allow that. Instead you have to use the method add.

But, your code has problems with design - overriding a with temp inside the recursion is wrong (you are just overriding the method pointer to a)

You have to return a merged list instead:

public List<String> mergeSort(List<String> a)
{
    if(a.size() <= 1)
    {
        return a;
    }

    int mid = a.size() / 2;
    List<String> left = a.subList(0, mid);
    List<String> right = a.subList(mid, a.size());

    return merge(mergeSort(left), mergeSort(right));
}

public List<String> merge(List<String> left, List<String> right)
{
    ArrayList<String> temp = new ArrayList<>(left.size() + right.size());

    int indexLeft = 0; //index for left array
    int indexRight = 0; //index for right array

    while(indexLeft < left.size() && indexRight < right.size())
    {
        if((left.get(indexLeft).compareTo(right.get(indexRight))) < 0)
        {
            temp.add(left.get(indexLeft++));
        }
        else
        {
            temp.add(right.get(indexRight++));
        }
    }
    while(indexLeft < left.size())
    {
        temp.add(left.get(indexLeft++));
    }
    while(indexRight < right.size())
    {
        temp.add(right.get(indexRight++));
    }

   return temp;
}