How do I solve this StackOverflowError?

Question

In this section of my MergeSort program, I am recursively dividing a unsorted array called "arr". To do this I create two subarrays, "leftArr" and "rightArr", then I fill "leftArr" and "rightArr" with the first half of "arr" and the second half of "arr" respectively. Afterwards I will use recursion to divde / sort leftArr and rightArr.

Just wanted clarify: mid = arr.length;

To initialise the rightArr I do the following:

 double halfLength = arr.length * 0.5; 
    if((!(halfLength < 0)) && (!(0 < halfLength))){
       // if right array is an even num, length of right array is mid
       rightArr = new int [mid];
   } else 
   {
       // else right arrays length is mid + 1
       rightArr = new int[mid + 1];
   }

When I do this I get no errors:

if(arr.length % 2 == 0){
       // if right array is an even num, length of right array is mid
       rightArr = new int [mid];
   } else 
   {
       // else right arrays length is mid + 1
       rightArr = new int[mid + 1];
   }

But my project doesn't allow me to use the modulus operator "%" and the "==" operator.

Im not getting any syntax error. All i see in the console window is: " Exception in thread "main" java.lang.StackOverflowError ".

The Complete recursive method looks like this:

 public int[] mergeSort(int[] arr) {

   if (arr.length < 2){
       return arr;  // if array has only one element, its already sorted 
   }
   int mid = arr.length / 2;     // find midpoint of array 

   int leftArr[] = new int [mid];   // create left subarray of length mid 
   int rightArr[];                  // create right subarray 

   /* if(arr.length % 2 == 0){
       // if right array is an even num, length of right array is mid
       rightArr = new int [mid];
   } else 
   {
       // else right arrays length is mid + 1
       rightArr = new int[mid + 1];
   }*/
    double halfLength = arr.length * 0.5; 
    if((!(halfLength < 0)) && (!(0 < halfLength))){
       // if right array is an even num, length of right array is mid
       rightArr = new int [mid];
   } else 
   {
       // else right arrays length is mid + 1
       rightArr = new int[mid + 1];
   }

   // create a resultArr of size arr, to store the sorted array 
   int resultArr[] = new int [arr.length];

   int i = 0;
   // Copy first half of arr[] into leftArr[]
   while(i < mid){  
       leftArr[i] = arr[i];
        i = i + 1;
   }
   int j = mid;
   int indexOfRight = 0;
   // Copy second half of arr into rightArr 
   while(j < arr.length){
       rightArr[indexOfRight] = arr[j];
       indexOfRight = indexOfRight + 1; 
       j = j + 1;
   }

   // Recursively call mergeSort to sort leftArr and rightArr
   leftArr = mergeSort(leftArr);
   rightArr = mergeSort(rightArr);

   // merge leftArr and rightArr into a resultant Array, and then return the resultArr 
   return resultArr = merge(leftArr, rightArr);

}

This is how I merge:

public int[] merge(int[] a1, int[] a2) {
  // TO BE COMPLETED
   int lengthOfRes = a1.length + a2.length;
   int resArr[] = new int [lengthOfRes];    // create resultant array of size a1 + a2

   int a1Index = 0;
   int a2Index = 0;
   int resIndex = 0;

   while((a1Index < a1.length) || (a2Index < a2.length))
   {
       if((a1Index < a1.length) && (a2Index < a2.length)){
           // if a1's element is <= a2's element, then insert a1's elem in resArr
           if(a1[a1Index] < a2[a2Index]){
               resArr[resIndex] = a1[a1Index];
               a1Index = a1Index + 1;
                resIndex = resIndex + 1;
           } else
             // else, insert a2's elem in resArr   
           {
               resArr[resIndex] = a2[a2Index];
               a2Index = a2Index + 1;
               resIndex = resIndex + 1;
           }
       }
       // Here, if there are any of a1's elements left over, then insert them into resArr
       else if(a1Index < a1.length){
            resArr[resIndex] = a1[a1Index];
            a1Index = a1Index + 1;
            resIndex = resIndex + 1;
       }
        // Here, if there are any of a2's elements left over, then insert them into resArr
       else
       {
           resArr[resIndex] = a2[a2Index];
            a2Index = a2Index + 1;
            resIndex = resIndex + 1;
       }
   }
   return resArr;   // return the resulting array

}

How can I fix this problem?

Thanks in advance!

Answer 1

This algorithm is not sorting anything. You are only breaking the array recursively, but there isn't any comparison.

This site have a good explanation about merge sorting algorithm: http://algs4.cs.princeton.edu/22mergesort/ http://algs4.cs.princeton.edu/22mergesort/Merge.java.html

It's worth studying it.

The problem is that this code

double halfLength = arr.length * 0.5; 
if((!(halfLength < 0)) && (!(0 < halfLength)))

do not determine if the arr.length is even. Try this:

    public boolean isEven(int number) {
      // return (number - (number / 2) * 2) == 0;
      return (!((number - (number / 2) * 2) > 0)) && (!((number - (number / 2) * 2) < 0));
    }

Here is another method without division, mod or equals operations

    public boolean isEven(int number) {
        number = number < 0 ? number * -1 : number;
        if (number < 1) {
            return true;
        }
        if (number > 0 && number < 2) {
            return false;
        }

        return isEven(number - 2);
    }