MergeSort - ArrayIndexOutOfBoundsException

Question

I am sorry if this has already been answered somewhere, I have spent over an hour searching through many previous questions and none of them were able to help me with this error.

I randomly receive an error, probably 70% of the time:

--------------------Configuration: MergeSort - JDK version 1.7.0_45 <Default> - <Default>-    -------------------

Random array: 17 14 3 4 1 10 13 9 3 1 6 9 10 2 17 8 10 5 7 8 
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 20

at MergeSort.merge(MergeSort.java:64)
at MergeSort.mergeSort(MergeSort.java:26)
at Driver.main(Driver.java:18)

Process completed.

Line 64 would refer to: "scratch[scratch_index] = list[i];"

public void merge(int[] list, int first, int middle, int last)
{
    int[] scratch = new int[list.length];

    int midpoint = (first+last)/2;

    int left_index = first;
    int right_index = middle + 1;
    int scratch_index = left_index;

    while((left_index <= midpoint) && (right_index <= last))
    {
        if(list[left_index] <= list[right_index])
        {
            scratch[scratch_index] = list[left_index];
            left_index +=1;
        }
        else
        {
            scratch[scratch_index] = list[right_index];
            right_index +=1;
        }
        scratch_index +=1;
    }

    for(int i=left_index;i<=midpoint;i++)
    {
        scratch[scratch_index] = list[i];
        scratch_index +=1;
    }
    for(int i=right_index;right_index<=last;i++) // I am line 64
    {
        scratch[scratch_index] = list[i];
        scratch_index +=1;
    }
    for(int i=0;i<list.length;i++)
    {
        list[i] = scratch[i];
    }
}

This is my first question ever on this site, sorry if I have not formatted this question correctly, any advice is appreciated.

If any other information is needed to help me with solving this error, just let me know. Thank you!

Answer 1

At the comment // I am line 64 You are incrementing the i and not the right_index which will cause the index to keep increasing until reaching index out of bound, so replace this,

for(int i=right_index;right_index<=last;i++) // I am line 64

by this:

for(int i=right_index; i<=last;i++) 

Answer 2

Indexes use "zero-based numbering" >> https://en.wikipedia.org/wiki/Zero-based_numbering

String example = "01234";
System.out.println(example.size()); //Prints out 5
System.out.println(exmaple.indexOf("1")); //Prints out 1

Your for statement needs to be checking up TO the last index

for(int i=right_index;right_index<last;i++)

OR (not recommended)

for(int i=right_index;right_index<=last-1;i++) //Works, but not recommended due to conventions

//index       0  1  2 3 4 5  6  7 8 9 10 11 12 13 14 15 16 17 18 19
Random array: 17 14 3 4 1 10 13 9 3 1 6  9  10 2  17 8  10 5  7  8 
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 20