Merge Sort java implementation error

Question

Ok, so I am trying to implement a merge sort in java, but i am running into the following error in the splitting of the array:

Exception in thread "main" java.lang.IllegalArgumentException: 2 > 1
    at java.util.Arrays.copyOfRange(Arrays.java:3591)
    at MergeSortS.recMergeSort(MergeSortS.java:26)
    at MergeSortS.recMergeSort(MergeSortS.java:28)
    at MergeSortS.mergeSort(MergeSortS.java:17)
    at MergeSortM.main(MergeSortM.java:16)
Java Result: 1
BUILD SUCCESSFUL (total time: 1 second)

My code segment is as follows, please help me identify my issue here...:( I have purposely commented out recMergeSort(right) recursive call at the end because I want to correct the recMergeSort(left) call...

public void recMergeSort(int[] tempArray){
        if(tempArray.length>1){
            int mid=(tempArray.length)/2;

            int[] left=Arrays.copyOfRange(tempArray,0,mid);

            int[] right=Arrays.copyOfRange(tempArray,mid+1,tempArray.length-1);

            recMergeSort(left);
            //recMergeSort(array, right, mid+1, right.length-1);
        }
    }

EDIT Ok, so I checked another site and the javadoc on copyOfRange method requiring the following:

Parameters:
original - the array from which a range is to be copied
from - the initial index of the range to be copied, **inclusive**
to - the final index of the range to be copied, **exclusive**. (This index may lie outside the array.)

After fixing this as follows:

public void recMergeSort(int[] tempArray){
        if(tempArray.length>1){
            int mid=(tempArray.length)/2;

            int[] left=Arrays.copyOfRange(tempArray,0,mid+1);

            int[] right=Arrays.copyOfRange(tempArray,mid+1,tempArray.length);

            recMergeSort(left);
            //recMergeSort(array, right, mid+1, right.length-1);
        }
    }

I get the following error:

Exception in thread "main" java.lang.StackOverflowError

Please help me correct this issue...:(

Answer 1

It appears that you were getting bogged down by the Arrays.copyOfRange() method. Try this code instead:

public void recMergeSort(int[] tempArray){
    if (tempArray.length > 1 ){
        int mid=(tempArray.length)/2;                                       // mid = 2
        int[] left = Arrays.copyOfRange(tempArray, 0, mid);                 // [10, 20]
        int[] right = Arrays.copyOfRange(tempArray, mid, tempArray.length); // [30, 40, 50]

        recMergeSort(left);
        //recMergeSort(array, right, mid+1, right.length-1);
    }
}

Arrays.copyOfRange(array, lowIndex, highIndex) will copy accessing from the lowIndex inclusive and the highIndex exclusive. This means that the highIndex for the left copy should be the same as the lowIndex for the right copy.

Usage:

int[] tempArray = new int[] {10, 20, 30, 40, 50};
recMergeSory(tempArray);

Answer 2

The reason you got java.lang.StackOverflowError is because your left array will never become array of size 1. If it enters if block then it means mid minimum will be 1 as tempArray can be 2 for it to satisfy. Then when you are copying to left 0-2, you are copying all the element again to left and right is empty

Answer 3

Too many recursions I think. From Java documentation.

Thrown when a stack overflow occurs because an application recurses too deeply.

---

By the way: See what happens when tempArray.length equals 2.

Your code has a bug I think.

int mid=(tempArray.length)/2; //mid equals 1
//calls with params tempArray, 0, 2
int[] left=Arrays.copyOfRange(tempArray,0,mid+1); 
//calls with params tempArray, 2, 2
int[] right=Arrays.copyOfRange(tempArray,mid+1,tempArray.length);

The last line is the problem. The length is 2, the second parameter is 2 and the third parameter is 2. The length of the returned array will be 0.

Answer 4

The stack overflow is a problem relating to the fact that for every call to recMergeSort you are creating two new arrays. This is called log(n) times, and causes the stack to become full.

To fix it you can either increase the stack size (see: What is the maximum depth of the java call stack? ) or you can refactor your code to use in place sorting by changing the parameters of recMergeSort(int[] tempArray) to recMergeSort(int[] unSortedArray, int startIndex, int endIndex).

For clarity: first call to it would be recMergeSort(array, 0, array.length-1), which would then call recMergeSort(array, startIndex, endIndex/2) and recMergeSort(array, (endIndex/2)+1, endIndex)

Answer 5

After factoring in all the errors you pointed out, I got it to working by changing the following along with the edits on the OP:

int mid=(tempArray.length-1)/2;

Thank you all for your support. I wasted one whole day trying to figure out this mess!