Сортировка слиянием выдает StackOverflowError

У меня есть простая функция сортировки слиянием в Java, которая для списка с длиной более 3 выдает исключение StackOverFlow, я каждый раз передаю объект массива с его смещением для создания хранилища стека, но выдает исключение stackOverFlow !! в чем проблема ??

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];
    }

}}

java oop mergesort stack-overflow
person abbas hoseini    schedule 25.10.2015    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы вычисляете неправильный средний индекс.

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

должно быть

int m=(h+l)/2;

Вероятно, поэтому ваша рекурсия никогда не заканчивается.

У вас также есть некоторые ошибки в вашем методе merg:

Изменять

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
    ...
person Eran    schedule 25.10.2015