MergeSort ArrayList IndexOutOfBoundsError

[dbsp]

I am trying to sort an ArrayList of Strings using the Merge Sort algorithm. However, I am having an error where it occurs on line 67 result.set(i,right.get(r)); Where I get the IndexOutOfBoundsException. I have tried printing out the index of the result, and it seems to be that I am trying to access the i element (which is result's size) However, I am not sure where in the code am I setting i to result's size. I am new to Java so much help will be appreciated!

import java.util.*;

public class MergeSort
{
   public static void sort(ArrayList<String> s)
   {
      if (s.size() < 2)
      {
         return;
      }

      int mid = (s.size())/2;

      ArrayList<String> left = new ArrayList<String>();

      int i;
      for (i = 0; i < mid; i++)
      {
          left.add(s.get(i));

      }

      ArrayList<String> right = new ArrayList<String>();

      for ( ; i < s.size(); i++)
      {
          right.add(s.get(i));
      }

      sort(left);
      sort(right);

      merge(s, left, right);
   }

   private static void merge(ArrayList<String> result, ArrayList<String> left, ArrayList<String> right)
   {
        int i = 0;
        int l = 0;
        int r = 0;

        while (l < left.size() && r < right.size())
        {
            if(right.get(r).compareTo(left.get(l)) > 0)
            {
                result.set(i,left.get(l));
                l++;
            }
            else
            {
                result.add(i,right.get(r));
                r++;
            }

             i++;
        }

        while (l < left.size())
        {
            result.set(i,left.get(l));
            l++;
            i++;
         }

        while (r < right.size())
        {
            result.set(i,right.get(r));
            r++;
            i++;
        }
    }

}

[wen_cai]

Umm... You are increasing the value of i everytime you go through a loop.

while (l < left.size() && r < right.size())
    {
        if(right.get(r).compareTo(left.get(l)) > 0)
        {
            result.set(i,left.get(l));
            l++;
        }
        else
        {
            result.add(i,right.get(r));
            r++;
        }
         i++;
    }

This while loop is half of the array.

while (l < left.size())
{
result.set(i,left.get(l));
l++;
i++;
}

And this while loop is the other half of the array.

At this point, i should be the full size of the array right? Then the below while loop while go over the size of your array.

while (r < right.size())
{
result.set(i,right.get(r));
r++;
i++;
}