ArrayOutOfBounds Exception Merge Sort

Question

I'm working on Merge Sort, and an ArrayIndexOutOfBoundsException is being thrown. I've been combing the code looking for the error and cannot find it. The exception stack trace says it is coming from my merge function on line 77 which is temp[current3++] = list2[current2++];. Line 102 is merge(firstHalf, secondHalf, list); and line 93 is mergeSortRoutine(firstHalf);. Any and all help is greatly appreciated. Thank you for your time.

Below are the two functions:

//this function will merge two arrays
private static void merge(Integer[] list1, Integer[] list2, Integer[] temp){
    int current1 = 0; //current index in list1
    int current2 = 0; //current index in list2
    int current3 = 0; //current index in temp

    while((current1 < list1.length) && (current2 < list2.length)){

        if(list1[current1].intValue() < list2[current2].intValue()){
            temp[current3++] = list1[current1++];
        }
        else{
            temp[current3++] = list2[current2++];
        }
    }

    while(current1 < list1.length){
        temp[current3++] = list2[current2++];
    }

    while(current2 < list2.length) {
        temp[current3++] = list2[current2++];
    }
}

//merge sort function
private static void mergeSortRoutine(Integer[] list){

    if(list.length > 1){

        //merge sort the first half
        Integer[] firstHalf = new Integer[(list.length)/2];
        System.arraycopy(list, 0, firstHalf, 0, (list.length)/2);
        mergeSortRoutine(firstHalf);

        //merge sort the second half
        int secondHalfLength = list.length - ((list.length)/2);
        Integer[] secondHalf = new Integer[secondHalfLength];
        System.arraycopy(list, (list.length)/2, secondHalf, 0, secondHalfLength);
        mergeSortRoutine(secondHalf);

        //merge firstHalf with secondHalf into list
        merge(firstHalf, secondHalf, list);
    }
}

Below is the stack trace:

java.lang.ArrayIndexOutOfBoundsException: 1
at Merge.merge(Merge.java:77)
at Merge.mergeSortRoutine(Merge.java:102)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.mergeSortRoutine(Merge.java:93)
at Merge.main(Merge.java:27)
at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method)
at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:62)
at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43)
at java.lang.reflect.Method.invoke(Method.java:498)
at com.intellij.rt.execution.application.AppMain.main(AppMain.java:147)

you are checking for current2 < list2.length in your loop but then you go and set it to a higher value list2[current2++] — Scary Wombat
– Scary Wombat, Commented Feb 15, 2017 at 1:59
@ScaryWombat Awesome! Thank you for the extra set of eyes. Got it working! Thanks again — user5924094
– user5924094, Commented Feb 15, 2017 at 2:06

bluecanary · Accepted Answer · 2017-02-15 02:06:27Z

2

As Scary Wombat says, in your final while loop you're checking current2 and then incrementing it.

In addition to that, you're incrementing current2 in your second-to-last while loop, while(current1 < list1.length). I think you probably intended that statement to be temp[current3++] = list1[current1++].

answered Feb 15, 2017 at 2:06

bluecanary

815 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

user5924094 Over a year ago

Awesome! thank you for the extra set of eyes! I got it working. Thanks again.

Collectives™ on Stack Overflow

ArrayOutOfBounds Exception Merge Sort

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related