CODEWITHSUNDEEP
javasortingrecursionmergemergesort
taralee98
taralee98

Reputation: 127

Merge sort throws ArrayOutOfBounds error in the copy over step?

I am trying to implement a generic merge sort algorithm, which uses a temp array to store the merged parts and then copies over the sorted data. However, the program keeps failing in the copy over step (the last while loop) and throws an ArrayIndexOutOfBounds exception. I am confused why this is happening!

I know that it is simpler to use Array.copy for this program but I am trying to practice with loops.

public static <E extends Comparable<E>> void mergeSort2(E[] array) {
    mergeSortHelper2(array, 0, array.length - 1);
}

private static <E extends Comparable<E>> void mergeSortHelper2(E[] array, int firstIndex, int lastIndex) {
    if (firstIndex >= lastIndex) {
        return;
    }
    //otherwise divide
    int middle = (firstIndex + lastIndex) / 2;

    //conquer with recursion
    mergeSortHelper2(array, firstIndex, middle);
    mergeSortHelper2(array, middle + 1, lastIndex);

    //combine: take in the original array, and all indices
    merge2(array, firstIndex, middle, middle + 1, lastIndex);
}

private static <E extends Comparable<E>> void merge2(E[] array, int leftFirst, int leftLast, int rightFirst, int rightLast) {
    E[] temp = (E[]) Array.newInstance(array.getClass().getComponentType(), (rightLast - leftFirst + 1));
    int indexLeft = leftFirst;
    int indexRight = rightFirst;
    int index = 0;

    while (indexLeft <= leftLast && indexRight <= rightLast) {
        if (array[indexLeft].compareTo(array[indexRight]) < 0) {
            temp[index++] = array[indexLeft++];
        }
        else {
            temp[index++] = array[indexRight++];
        }
    }

    while (indexLeft <= leftLast) {
        temp[index++] = array[indexLeft++];
    }
    while (indexRight <= rightLast) {
        temp[index++] = array[indexRight++];
    }

    int newIndex = 0;

    while (newIndex != temp.length - 1) {
        array[newIndex++] = temp[newIndex++];
    }
}

Upvotes: 0

Views: 71

Answers (2)

Armine
Armine

Reputation: 1695

You have to have 2 temp arrays: just have a look at Merge-Sort algorithm implementation

Upvotes: 0

Bill the Lizard
Bill the Lizard

Reputation: 405995

array[newIndex++] = temp[newIndex++];

You're incrementing newIndex twice on that line. Split that into two lines of code, one to increment, then one to use it as an array index.

Note: This pattern works in other places in your code because you're incrementing two different indices. For example.

temp[index++] = array[indexLeft++];

It's getting out of range in the final loop because of the double increment on the same variable when you reach the end of your arrays.

Upvotes: 1

Related Questions