Java: Mergesort stackoverflow error

Question

I have create a top-down implementation of Mergesort in Java but it's giving StackOverFlow error, I am unable to debug. Any leads?

/**
* Merge Sort
*
* Implementation in based on the concepts according to CLRS
*/
import java.util.Arrays;
import java.io.*;

    class mergesort{

      static int A[] = {23,45,10,2,78,32,89,90,1,64};

      static int B[] = new int[A.length]; 

      public static void main(String args[]) throws IOException{

    //     Set up output to a file
        PrintStream ps = new PrintStream(new FileOutputStream("out.txt"));
        PrintStream pserr = new PrintStream(new FileOutputStream("err.txt"));
        System.setOut(ps);
        System.setErr(pserr);

        MERGE_SORT(A,0,9);

        // print sorted array
        for(int i=0;i<=9;i++){
          System.out.print(Integer.toString(B[i])+" ");
        }
      }

      /**
       * Function to merge two sorted arrays
       */
      private static void MERGE(int A[],int p,int q,int r){
        // variables
        int lLimit,rLimit,lp,rp,k;

        // initialize variables
        lp=0;rp=0;k=0;

        // find number of elements in left and right arrays
        lLimit = q-p+1;
        rLimit = r-q;

        // create lists
        int L[] = new int[lLimit];
        int R[] = new int[rLimit];
        for(int i=0;i<lLimit;i++){
          L[i] = A[i];
        }
        for(int i=0;i<rLimit;i++){
          R[i] = A[i+lLimit];
        }

        // sort individual lists
        for(int i=0;i<=r;i++){       // runs r times
          if(lp>lLimit-1 || rp>rLimit-1) return;   // to handle ArrayIndexOutOfBounds
          if(L[lp] < R[rp]){
            // copy L[lp] to A[k];
            A[k] = L[lp];
            lp++;                    // this step could lead to ArrayIndexOutOfBounds error on next check for lp
          }else{
            A[k] = R[rp];
            rp++;                    // this step could lead to ArrayIndexOutOfBounds error on next check for rp
          }
          // increment array A's pointer k
          k++;
        }
      }

      /**
       * Following procedure will result in the creation of individual sorted items
       */
      private static void MERGE_SORT(int A[],int p,int r){
          if(p<r){
            int q = (r-p)/2;   // remember, r > p
            MERGE_SORT(A,p,q); 
            MERGE_SORT(A,q+1,r);
            MERGE(A,p,q,r);
          }
      }
    }

Output:

Exception in thread "main" java.lang.StackOverflowError
    at mergesort.MERGE_SORT(mergesort.java:77)
    at mergesort.MERGE_SORT(mergesort.java:78)
    at mergesort.MERGE_SORT(mergesort.java:78)
    at mergesort.MERGE_SORT(mergesort.java:78)
    at mergesort.MERGE_SORT(mergesort.java:78)
    at mergesort.MERGE_SORT(mergesort.java:78)
    at mergesort.MERGE_SORT(mergesort.java:78)
    at mergesort.MERGE_SORT(mergesort.java:78)
    at mergesort.MERGE_SORT(mergesort.java:78)
......

The StackOverflowError says, the call hierarchy is too deep for your stack size, so probably a not ending recursion. By the first viewing ... what happens if p equals r in MERGE_SORT, does the recursion end then? BTW you might take a look into Java Coding Conventions especially Naming Conventions. — yasd
– yasd, Commented Oct 31, 2015 at 11:13

Eran · Accepted Answer · 2015-10-31 11:29:55Z

4

You are not computing the middle of the range correctly in your MERGE_SORT method.

int q = (r-p)/2;

should be

int q = (r+p)/2;

Beside that issue, your MERGE method also has problems. You initialize the L and R arrays incorrectly. The L array should be assigned values from the p to q indices of the input array (not from 0 to q-p). The R array should be assigned values from the q+1 to r indices of the input array.

edited Oct 31, 2015 at 11:29

answered Oct 31, 2015 at 11:00

Eran

395k57 gold badges726 silver badges793 bronze badges

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

2 Comments

Rajat Saxena Over a year ago

I corrected the clause and now it runs fine but there are some problem in the output. Here is the final output: 2 10 10 32 45 78 89 90 1 64

Eran Over a year ago

@RajatSaxena Your MERGE method is also wrong. You seem to be assuming the the left range always starts at 0, which it doesn't. It starts at p.

Collectives™ on Stack Overflow

Java: Mergesort stackoverflow error

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related