CODEWITHSUNDEEP
javaalgorithm
JKK
JKK

Reputation: 446

Getting a stack overflow error in my Merge Sort

I am getting a stack overflow error in my merge sort. Not sure why yet.

//BAD CODE BAD CODE
public static void main(String[] args) {
    int[] S = {3,4,6,2,5,3,7};
    mergesort(S, 1, 5);
    System.out.println(S);
}   

public static void mergesort(int[] S, int left, int right){
    if (right <= 1) { return; }
    int mid = (right + left) / 2;
    mergesort (S, left, mid);
    mergesort (S, mid+1, right);
    merge(S, left, mid, right); 
}

public static void merge(int[] S, int left, int mid, int right){
    int i, j;
    int[] aux = new int[S.length];

    for (i = mid+1; i > left; i--) {aux[i-1] = S[i-1];}
    for (j = mid; j < right; j++) {aux[right+mid-j] = S[j+1];}
    for (int k = left; k <= right; k++){
        if (aux[j] < aux[i]) {
            S[k] = aux[j--]; 
        } else{
            S[k] = aux[i++];
        }
    }
}
//END OF BAD CODE

Update

Thank you for all of the quick responses, I got it working and made some suggested changes. Copy and paste, try it out:

//GOOD CODE
package longest_sequence_proj;
import java.util.*;

public class MergeTest {

/**
 * @param args
 */
public static void main(String[] args) {
    int[] S = {3,4,6,2,5,3,7};

    mergesort(S, 0, 6);

    System.out.println(Arrays.toString(S));

}



public static void mergesort(int[] S, int left, int right){
    if (right <= left) { return; }
    int mid = (right + left) / 2;
    mergesort (S, left, mid);
    mergesort (S, mid+1, right);
    merge(S, left, mid, right);

    }

public static void merge(int[] S, int left, int mid, int right){
    int i, j;
    int[] aux = new int[S.length];

    for (i = mid+1; i > left; i--) {aux[i-1] = S[i-1];}
    for (j = mid; j < right; j++) {aux[right+mid-j] = S[j+1];}
    for (int k = left; k <= right; k++){
        if (aux[j] < aux[i]) {
            S[k] = aux[j--]; 
        } else{
            S[k] = aux[i++];
        }
    }
}
}

Upvotes: 2

Views: 4578

Answers (3)

amit
amit

Reputation: 178491

Your stop clause is wrong:

 if (right <= 1) { return; }

You actually want to stop when the size of the partial array used is smaller then one, so you are probably looking for:

if (right - left <= 1) { return; }

As a side note: 

System.out.println(S);

I guess it is not what you want (It does not print the array, rather the identifier of the object...)
In order to print the array use:

System.out.println(Arrays.toString(S));

Upvotes: 4

Christian Stieber
Christian Stieber

Reputation: 12496

Well, consider this:

int mid = (right + left) / 2;
...
mergesort (S, mid+1, right);

Starting with left=1 and right=5, mid becomes 3, so the recursive call is left=4 and right=5. This yields mid=9/2 which I guess is 4 in java, so we get another recursion with left=5 and right=5, which leads to mid=5 and a recursion for left=6 and right=5 and so on. "Right" never gets any smaller...

Upvotes: 2

RonK
RonK

Reputation: 9652

Your right branch of the mergesort call will never end.

Your stop condition is right <= 1 - but on the right branch of your call tree right will never be 1.

You should put a better end condition on your recursion - something that will actually end sometime.

Upvotes: 0

Related Questions