0

I've been doing some practice with sorting algorithms and I keep getting this error for my merge sort. I can't even scroll up to see what the original error was because it displays at SortTestPractice.mergesort etc. so many times I reach the upper limit on display. Any ideas as to what the error could be?

Here is my code for the chunk in question

public static ArrayList<String> mergeSort(ArrayList<String> testList)
  {
      ArrayList<String> left = new ArrayList<String>();
      ArrayList<String> right = new ArrayList<String>();
      int center;
          center = testList.size()/2;
          // copy the left half of testList into the left.
          for (int i=0; i<center; i++) {
                  left.add(testList.get(i));
          }

          //copy the right half of testList into the new arraylist.
          for (int i=center; i<testList.size(); i++) {
                  right.add(testList.get(i));
          }

          // Sort the left and right halves of the arraylist.
          left  = mergeSort(left);
          right = mergeSort(right);

          // Merge the results back together.
          merge(left, right, testList);
          return testList;
  }

The line it points me to is left = mergeSort(left);. My initial thought was that it wasn't recognizing when left and right contained only 1 piece of data and kept trying to split them. I came up with a quick fix for that by adding an if else statement but I still got the same error.

here is my merge function

private static ArrayList<String> merge(ArrayList<String> left, ArrayList<String> right, ArrayList<String> testList) {
// source: modified from http://www.codexpedia.com/java/java-merge-sort-implementation/
    int leftIndex = 0;
    int rightIndex = 0;
    int testListIndex = 0;

    // As long as neither the left nor the right ArrayList has
    // been used up, keep taking the smaller of left.get(leftIndex)
    // or right.get(rightIndex) and adding it at both.get(bothIndex).
    while (leftIndex < left.size() && rightIndex < right.size()) {
        if ( (left.get(leftIndex).compareTo(right.get(rightIndex))) < 0) {
            testList.set(testListIndex, left.get(leftIndex));
            leftIndex++;
        } else {
            testList.set(testListIndex, right.get(rightIndex));
            rightIndex++;
        }
        testListIndex++;
    }

    ArrayList<String> rest;
    int restIndex;
    if (leftIndex >= left.size()) {
        // The left ArrayList has been use up...
        rest = right;
        restIndex = rightIndex;
    } else {
        // The right ArrayList has been used up...
        rest = left;
        restIndex = leftIndex;
    }

    // Copy the rest of whichever ArrayList (left or right) was not used up.
    for (int i=restIndex; i<rest.size(); i++) {
        testList.set(testListIndex, rest.get(i));
        testListIndex++;
    }
    return testList;
  }
  public static void hybridSort(ArrayList<String> testList)
  {
    int temp = 0;

      for (int i = 0; i<100; i++)
      {
       if (testList.get(i).compareTo(testList.get(i+1)) < 0)
       {
        temp++;
       }
      }
    if (temp >= 90)
    {
      insertionSort(testList);
    }
    else
    {
      mergeSort(testList);
    }
  }
}
Ryan Schubert
  • 1
  • 1
  • What does your merge function look like? – Steven Sep 21 '17 at 00:34
  • I added the merge function – Ryan Schubert Sep 21 '17 at 00:36
  • What is the line in question? – Avery246813579 Sep 21 '17 at 00:39
  • 1
    Add a check and just return if testList.size() <= 1. – rcgldr Sep 21 '17 at 00:45
  • @Steven added merge function – Ryan Schubert Sep 21 '17 at 00:49
  • @Avery246813579 the line in question is mentioned under the first chunk of code – Ryan Schubert Sep 21 '17 at 00:50
  • @rcgldr i think I tried something similar already, I put an if (left.size!=1) then do the mergesort function else merge() but it didn't work – Ryan Schubert Sep 21 '17 at 00:53
  • 1
    @RyanSchubert - consider what happens if testList.size == 3. left.size == 1 and right.size == 2. It would be simpler to check for testList.size <= 1. (The < 1 check only needed in case the original caller passes an empty list). – rcgldr Sep 21 '17 at 14:16
  • 1
    Truly a comment here: it is much more efficient to do a one time allocation of a list with a helper function and then use indexing to work with the sub-lists. Examples of bottom up and top down merge sort for an array of primitive integers can be seen in this [prior thread](https://stackoverflow.com/questions/46106922/mergesort-algorithm-whats-the-better-implementation-in-java/46107386#46107386) . – rcgldr Sep 21 '17 at 14:18

1 Answers1

0

Add this to the beginning of mergeSort function. You need a base case.

if(testList.size() <= 1){ return testList; }

--- edit @rcgldr commented the same before i did

Steven
  • 604
  • 6
  • 11