CODEWITHSUNDEEP
javaunixrecursionstack-overflow
user3827690
user3827690

Reputation: 21

java stack overflow error?

Exception in thread "main" java.lang.StackOverflowError
at Search.mergeSort(Search.java:41)
at Search.mergeSort(Search.java:43)
at Search.mergeSort(Search.java:43)
at Search.mergeSort(Search.java:43)
at Search.mergeSort(Search.java:43)

I keep getting this error when I try to run my program. My program is supposed to take string input from a file and sort it using this algorithm. Any ideas? Problematic lines from code:

public static void mergeSort(String[] word, int p, int r){
int q;
if(p<r){
q=p+r/2;
mergeSort(word,p,q);
mergeSort(word, q+1,r);
merge(word, p, q, r);
}
}

EDIT

These two functions sort the String array by dividing the array in half, sorting each half separately, and merging them together. Int q is the halfway point, and the arrays being evaluated are from word[p] to word[q] and word[q+1] to word[r]. here's merge function:

public static void merge(String[] word, int p, int q, int r){
    int n1 = q-p+1;
    int n2 = r-q;
    String[] L = new String[n1];
    String[] R = new String[n2];
    int i, j, k;

    for(i=0; i<n1; i++) L[i] = word[p+i];
    for(j=0; j<n2; j++) R[j] = word[q+r+1];
    i=0; j=0;
    for(k=p; k<=r; k++){
        if(i<n1 && j<n2){
            if(L[i].compareTo(R[j])<0){
                word[k] = L[i];
                i++;
            }else{
                word[k] = R[j];
                j++;
            }
        }else if(i<n1){
            word[k] = L[i];
            i++;
        }else if(j<n2){
            word[k] = R[j];
            j++;
        }
    }

Upvotes: 0

Views: 132

Answers (3)

SamC
SamC

Reputation: 31

When making recursive methods, you need some base case, otherwise you'll get infinite recursion like you are right now.

In your mergeSort method, you don't have a base case. You need to put a check in to see if the part you're sorting is already sorted; if word[p..r] is sorted, then you should not call mergeSort

Upvotes: 0

Stephen C
Stephen C

Reputation: 718886

The problem is that your calculation of q is incorrect. It is supposed to be the halfway point between p and r, and the way to calculate that is:

 q = p + (r - p) / 2;

or

 q = (p + r) / 2;

But you've written:

 q = p + r / 2;

which is equivalent to

 q = p + (r / 2);

Upvotes: 0

djechlin
djechlin

Reputation: 60778

Walk through with a debugger. You'll see exactly how it's leading to an infinite recursion. IDEs (Eclipse, IntelliJ) have them built in.

Upvotes: 2

Related Questions