simple recursive merge sort Stack java.lang.StackOverflowError

Question

I have a simple recursive merge sort, I am just try to sort an array list of Integers that implement Comparable. I don't under stand why I am getting an error, when it runs it prints out the ArrayList of random Integers that I created and then it prints

no error yet

Exception in thread "main" java.lang.StackOverflowError

and then it repeats

at MergeTemplate.rMerge(MergeTemplate.java:38)

a bunch of times until it finally says

Process complete

import java.util.*;
public class MergeTemplate{
private ArrayList <Comparable> temp1=new <Comparable> ArrayList();
int num;
Random ar=new Random();
public MergeTemplate(){
    num=25;
}
  public MergeTemplate(int n){
    num=n;
  }
      public ArrayList <Comparable> fillArray(){
          ArrayList <Comparable> ar1=new <Comparable> ArrayList();
          for(int i=0;i<num; i++)
              ar1.add(ar.nextInt(11));
          screenOutput(ar1);
      return ar1;
      }
      public void screenOutput(){
          for(Comparable x: temp1)
              System.out.print(x+ " ");
          System.out.println();
      }
      public void screenOutput(ArrayList <Comparable> temp){
          for(Comparable x: temp)
              System.out.print(x+ " ");
          System.out.println();
      }
      public void rMerge(ArrayList <Comparable> rList){
          rMerge(rList, 0, rList.size()-1);
      }

      public void rMerge(ArrayList <Comparable> rList, int first, int last){
          if (first-last==0){
              System.out.println("no error yet");
          }
          else{
              rMerge(rList, first, last/2);
              rMerge(rList, last/2 + 1, last);
              merge(rList, first, last);
          }
      }
      public void merge(ArrayList <Comparable> a, int first, int last){
          Comparable placeHolder;
          if(a.get(first).compareTo(a.get(last))>1){
              placeHolder=a.get(first);
              a.set(first, a.get(last));
              a.set(last, placeHolder);
          }
      }
}

public class Tester {
    public static void main(String[] args) {
    MergeTemplate one=new MergeTemplate(8);
    one.rMerge(one.fillArray());
    }
}

Those methods could _all_ be `static`, and every object field could be moved or removed. `num` and `ar` are never used outside of the `fillArray()` method. `num` should be either a private static constant or a parameter to `fillArray()`, while `ar` should be either a private static field or declared and created inside `fillArray()` (or _maybe_ a parameter). `temp1` can be deleted, along with the only method that refers to it, `screenOutput()`. That method only "uses" `temp1` to do literally nothing, and is itself never called, anyway. — Kevin J. Chase, Apr 03 '17 at 05:53
n is the size of the array list and ar is a object of type random so it is what creates the random numbers that go in the array list, i just forgot to make it private, and I just forgot to take out somethings like temp1 because i edited the code to include what was only contributing to the error, but I guess I forgot to take some things out. — noah D, Apr 03 '17 at 15:09

score 0 · Answer 1 · answered Apr 03 '17 at 01:27

0

Your merge method has an error, it doesn't iterate over the all list to verify the order result.

answered Apr 03 '17 at 01:27

edwindh

99
1
4

score 0 · Answer 2 · answered Apr 03 '17 at 01:31

0

I think you should add (last < first) to your condition to be:

if (first-last==0 && last < first){
   System.out.println("no error yet");
}

answered Apr 03 '17 at 01:31

Fady Saad

1,169
8
13

first-last will never be 0 if first and last are not the same number so if i include last – noah D Apr 03 '17 at 15:10

bichito · Answer 3 · 2017-04-03T02:07:26.570

0

Your error occurs in

rMerge(rList, first, last/2);

When first equals 2 last goes to less than 2, actually last equals to 0 and keeps on calling itself. You need a check that there is 1 element.

Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted)

Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

from wikipedia.

edited Apr 03 '17 at 02:07

answered Apr 03 '17 at 01:45

bichito

1,406
2
19
23

when first equals 2 doesn't last equal 2? cause that is what i get when i try to do it by hand. because 2/2 +1 = 2, and so last would just be 2. – noah D Apr 03 '17 at 15:35
If you had used the debugger and checked the values of first and last then those are the values that you would have found. That is what your code was doing – bichito Apr 03 '17 at 16:54
does JCreator have a debugger? – noah D Apr 03 '17 at 17:12
I have not used but if it doesn't there is always jdb. Learning to use a debugger will save you a lot of time – bichito Apr 03 '17 at 17:15

score 0 · Accepted Answer · answered Apr 03 '17 at 06:12

You need one more key to represent the split point to divide the elements appropriately. The merge () method also needs to be re-implemented to iterate over all target elements. The complete code with an implementation of the rMerge() method adding a single key called mid and an implementation of the merge() method as shown below.

import java.util.ArrayList;
import java.util.Random;

public class MergeTemplate {

    private Random random = new Random();

    private ArrayList<Comparable> temp1 = new ArrayList<>();
    private int num;


    public MergeTemplate() {
        this.num = 25;
    }

    public MergeTemplate(int num) {
        this.num = num;
    }

    public ArrayList<Comparable> fillArray() {
        ArrayList<Comparable> ar1 = new ArrayList<>();

        for (int i = 0; i < num; i++) {
            ar1.add(random.nextInt(11));
        }
        screenOutput(ar1);
        return ar1;
    }

    public void screeOutput() {
        for (Comparable x : temp1) {
            System.out.println(x + " ");
        }
        System.out.println();
    }

    public void screenOutput(ArrayList<Comparable> temp) {
        for (Comparable x : temp) {
            System.out.println(x + " ");
        }
        System.out.println();
    }

    public void rMerge(ArrayList<Comparable> rList) {
        rMerge(rList, 0, rList.size() - 1);
    }

    public void rMerge(ArrayList<Comparable> rList, int first, int last) {

        int mid = 0;
        if (first >= last) {
            System.out.println("no error yet");
        } else {
            mid = (first + last) / 2;
            rMerge(rList, first, mid);
            rMerge(rList, mid + 1, last);
            merge(rList, first, mid, last);
        }
    }

    public void merge(ArrayList<Comparable> a, int first, int mid, int last) {
        int i, j, k, m;

        i = first;
        j = mid + 1;
        k = first;

        ArrayList<Comparable> tempList = new ArrayList<>();

        // compare two divided parts
        while (i <= mid && j <= last) {
            if (a.get(i).compareTo(a.get(j)) < 1) {
                tempList.add(a.get(i));
                i++;
            } else {
                tempList.add(a.get(j));
                j++;
            }
            k++;
        }

        if (i > mid) {
            for (m = j; m <= last; m++) {
                tempList.add(a.get(m));
                k++;
            }
        } else {
            for (m = i; m <= mid; m++) {
                tempList.add(a.get(m));
                k++;
            }
        }

        for (i = 0, j = first; i < tempList.size(); i++, j++) {
            a.set(j, tempList.get(i));
        }

    }

}

It is missing a line of code still.You need to add temp1 = rList after calling merge inside rMerge otherwise you are merging thin air because rList is the working array. And nobody holds a reference to it — bichito, Apr 03 '17 at 12:47
I think rList does not need to keep intermediate results in temp1 because it is used only when reading the merge target data and storing merge operation results. Since the data stored in rList is used as the target of the next merge after the previous merge is completed, it is unlikely that the data will be corrupted. — Ray, Apr 04 '17 at 07:00
if I had a big set of data, what would be faster? 1. sorting the values in the original array with out the use of a secondary array, or 2. using a second array like this answer does? — noah D, Apr 10 '17 at 00:50
In fact, the k++ in the above program is useless. The k variable was used to point to the index of array when using array to store intermediate merged results. However, the above program uses ArrayList instead of array, there is no need to maintain Index. — Ray, Apr 17 '17 at 09:18
And the tempList is used to store intermediate merged result. So this algorithm requires the space complexity of O (n). If you need space complexity of O(1), see this link. http://stackoverflow.com/questions/2571049/how-to-sort-in-place-using-the-merge-sort-algorithm — Ray, Apr 17 '17 at 09:33

simple recursive merge sort Stack java.lang.StackOverflowError

4 Answers4