current community

your communities

more stack exchange communities

Stack Exchange
tour help
stack overflow careers
Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.
up vote 0 down vote favorite 
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++;
        }
    }
share|improve this question
2  
Post the full code including merge because we don't know what's going on in merge. It'd be helpful to know what's on line 43 as well. –  chubbsondubs Jul 11 '14 at 2:24
    
It's pretty unusual for a function to call itself twice in two lines. –  aliteralmind Jul 11 '14 at 2:33
1  
"Infinite" recursion. Unless the if statement caps the recursion, this will happen. A little hard to get one's head around what the p/q/r computations are doing and how that might (or might not) end the recursion. –  Hot Licks Jul 11 '14 at 2:36
    
@chubbsondubs - I don't see how what goes on in merge could affect how deep recursion occurs. It's purely a function of the p/q/r stuff. –  Hot Licks Jul 11 '14 at 2:38
    
Insert a println statement to print out the p, q, and r values for each recursion. (Note that this will be A LOT of data, since growth is exponential.) (It would help understanding to add a couple of extra parms to indicate recursion depth and whether left or right call, and print those too.) –  Hot Licks Jul 11 '14 at 2:43

3 Answers 3

up vote 1 down vote

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

share|improve this answer
up vote 1 down vote

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);
share|improve this answer
    
I did this and it seemed to fix the stack overflow error but a new error was generated: Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 12 at Search.merge(Search.java:58) at Search.mergeSort(Search.java:46) at Search.mergeSort(Search.java:44) at Search.mergeSort(Search.java:44) at Search.mergeSort(Search.java:45) at Search.main(Search.java:31) –  user3827690 Jul 11 '14 at 3:29
    
I think you need to follow djechlin's advice. –  Stephen C Jul 11 '14 at 4:20
up vote 2 down vote

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

share|improve this answer
1  
Unfortunately, recursive problems can quickly get out of control and beyond one's ability to follow if you attempt to use only a debugger. You generally need some sort of "printed" trace as well. –  Hot Licks Jul 11 '14 at 2:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.