CODEWITHSUNDEEP
java
Jonathan Zier
Jonathan Zier

Reputation: 170

Recursive sorting method not stopping at the base case

For school, I am trying to write a recursive sorting algorithm. Yet for some reason it is not stopping at the base case and help would be greatly appreciated. The error is

java.lang.StackOverflowError

Here is the method:

 public static List recursiveMergeSort(List<Integer> list1){
    List<Integer> list = list1;
    List<Integer> listR = new ArrayList<>();
   List<Integer> listL = new ArrayList<>();


     int counter =0;

    if(list.size() == 1){
        return list;
    } else {

        for (int i = 0; i <list.size()/2-1; i++){
            listL.add(list.get(i));
        }

        for(int i = list.size()/2; i  < list.size()-1; i++) {
            listR.add(list.get(i));
        }

        recursiveMergeSort(listL);
        recursiveMergeSort(listR);

        list = merge(listL, listR);
        counter++;
    }
    return (list);
}

public static List merge(List<Integer> listL, List<Integer> listR){
    int leftIndex = 0;
    int rightIndex = 0;
    int listIndex = 0;
    List<Integer> list = new ArrayList<>();
    while(leftIndex < listL.size() && rightIndex < listR.size()){
        if(listL.get(leftIndex) <= listR.get(leftIndex)){
            listR.add(listIndex, listL.get(leftIndex));
            leftIndex = leftIndex + 1;

        }else {
            list.add(list.get(listIndex), listR.get(rightIndex));
            rightIndex = rightIndex +1;
        }
        listIndex = listIndex + 1;
    }
    if(leftIndex < listL.size()){
        copyRest(listL, leftIndex, list, listIndex);
    } else {
        copyRest(listR, rightIndex, list, listIndex);
    }
    return (list);
}

Thanks for the help!

Upvotes: 0

Views: 44

Answers (1)

mettleap
mettleap

Reputation: 1410

The problem lies in the two inner for loops:

    for (int i = 0; i <list.size()/2-1; i++){ // should be i<list.size()/2
        listL.add(list.get(i));
    }


    for(int i = list.size()/2; i  < list.size()-1; i++) { //should be i  < list.size()
        listR.add(list.get(i));
    }

Initially when you give an input of size 5, listR gets two elements (elements with indices 2 and 3) and in the recursive call for listR, none of the for loops get executed, so the recursive call goes on and on until you get an error

Upvotes: 1

Related Questions