Implementing MergeSort

Question

I have implemented a MergeSorting that takes a Generic Data type and a upper and lower index bound that stops the sorting after it passes those bounds. An example {85,31,321,6549,123,2,1,0} lower = 0 upper = 4 will yield [31,85,123,321,6549,2,1,0]. Although when Im testing my code it is giving a stackoverflow error, and I do not know why.

I have looked through my code and could not find the problem, maybe I do not have a edge case to break out of recursive call.

import java.util.ArrayList;
public class Sorts<T extends Comparable<? super T>> {
   public void merge(ArrayList<T> list, int start, int mid, int end)
   {
        ArrayList<T> tempArr = new ArrayList<T>(end - start);
        int leftidx = start;
        int rightidx = mid;
        while(true)
        {
            if (leftidx ==  mid)
            {
                tempArr.addAll(list.subList(rightidx,end)); 

                break;
            }
            else if (rightidx == end)
           {
                tempArr.addAll(list.subList(leftidx, mid));
                break;
           }

           T left = list.get(leftidx);
           T right = list.get(rightidx);

           int check = left.compareTo(right);

           if (check < 0) 
           {
               tempArr.add(left); 
               leftidx++; 
           }
           else
           {
               tempArr.add(right); 
               rightidx++; 
           }
        }

        for (int j = 0; j < tempArr.size(); j++)
        {
            list.set(start + j, tempArr.get(j));
        }




}
public void MergeSort(ArrayList<T> list, int start, int end) {

    int median = start + (end - start) / 2;
    MergeSort(list, start, median);
    MergeSort(list, median, end);
    merge(list, start, median, end);

   }
}

When I run a test, it is giving an error "java.lang.StackOverflowError" at line 82 which is MergeSort(list,start,median) in my mergesort clas. My tester class is:

public class SortsTester extends Sorts{
    public void mergeSortTester{
       Integer [] arr = {85,31,321,6549,123,2,1,0};
       ArrayList<Integer> ranArrLst = new ArrayList<>(Arrays.asList(arr));
       MergeSort(ranArrLst,0,7);
       System.out.println(Arrays.toString(ranArrLst.toArray()));
     }
}

`StackOverflowError` means you are calling a method recursively and there is no stop condition. Can you detect which of your methods is calling itself, and doesn't have a stop condition? — RealSkeptic, Apr 30 '19 at 11:06
And how does the constructor look like? The StackOverflow is apparently there and you didn't show it. Either you have some infinite loop somewhere or some recursive call and big set of data which cannot be processed this way. — NeplatnyUdaj, Apr 30 '19 at 11:07
Please read this question and its answers: [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173) — Axel, Apr 30 '19 at 11:37

score 0 · Answer 1 · answered Apr 30 '19 at 11:19

0

You should do nothing in MergeSort when there are less than two elements:

public void MergeSort(ArrayList<T> list, int start, int end) {
    if ((end - start) < 2) {
        return;
    }
    int median = start + ((end - start) / 2);
    MergeSort(list, start, median);
    MergeSort(list, median, end);
    merge(list, start, median, end);
}

answered Apr 30 '19 at 11:19

Ralf Renz

1,061
5
7

i was think of calling if(start >= end) then returning, would that yield the same ? – clumbzy1 Apr 30 '19 at 11:22

Implementing MergeSort

1 Answers1