CODEWITHSUNDEEP
javaoopstack-overflowmergesort
abbas hoseini
abbas hoseini

Reputation: 513

Merge sort throws StackOverflowError

I have a simple merge sort function in Java that for list with larger than 3 length throw StackOverFlow exception , I pass the array object each time with it's offset's to produce the stack storage but it throw stackOverFlow exception !! where is the problem ??

public class DiviedAndConquer {

/**
 * @param args
 */
public static void main(String[] args) {
    // TODO Auto-generated method stub
    DiviedAndConquer app=new DiviedAndConquer();
    Integer[] arr={3,5,1,8};
    app.mergSort(arr,0,arr.length-1);
    for(int i = 0;i<=arr.length-1;i++)
        System.out.print(arr[i]+" ");


}
public  void mergSort(Integer[] arr,int l,int h){
    if(h-l>0){
        int m=(h-l+1)/2;
        //int l=arr.length-h;
        mergSort(arr,l,m);
        mergSort(arr,m+1,h);
        merg(arr,l,h);
    }

}
public   void merg(Integer[] arr,int l,int h){
    Integer[] tarr=new Integer[h-l+1];
    for(int p=0;p<=h;p++)
        tarr[p]=0;
    int m=(h-l)/2;
    int j=m+1;
    int k=0;
    int i=l;
    while(i<=m && j<=h){
        if(arr[j]<arr[i]){
            tarr[k]=arr[j];
            j++;
        }
        else{
            tarr[k]=arr[i];
            i++;
        }
        k++;
    }

    if(i<=m){
        for(;i<=m;i++){
            tarr[k]=arr[i];
            k++;
        }
        k--;
    }
    else if(j<=h){
        for(;j<=m;j++){
            tarr[k]=arr[j];
            k++;
        }
        k--;
    }
    for(int z=0;z<=k;z++){
        arr[l+z]=tarr[z];
    }

}}

Upvotes: 1

Views: 404

Answers (1)

Eran
Eran

Reputation: 393996

You are computing an incorrect middle index.

int m=(h-l+1)/2;

should be

int m=(h+l)/2;

That's probably the reason your recursion never ends.

You also have some errors in your merg method :

Change 

public void merg(Integer[] arr,int l,int h) {
    Integer[] tarr = new Integer[h-l+1];
    for(int p=0;p<=h;p++)
        tarr[p]=0;
    int m=(h-l)/2;
    ...

to

public void merg(Integer[] arr,int l,int h){
    Integer[] tarr = new Integer[h-l+1];
    for(int p=0;p<tarr.length;p++) // corrected the range of the loop
        tarr[p]=0;
    int m=(h+l)/2; // the same fix of m calculation as before
    ...

Upvotes: 1

Related Questions