Simple Merge Sort in Java

Question

I'm trying to create a simple merge sort program within Java. I feel like it should work but when I go to run it I get a stack overflow error:

Stack overflow at MergeSort.mergeSort(MergeSort.java:24)

I have seen several other people on here have similar problems with such code but am struggling to fix mine. Any help would be appreciated.

Main code:

import static java.lang.System.*;
import java.util.Arrays;        

public class MergeSort {

    private static int passCount;

    public static void mergeSort(Comparable[] list)
    {
        passCount = 0;
        mergeSort(list, 0, list.length);
    }

    private static void mergeSort(Comparable[] list, int front, int back)  //O( Log N )
    {
        int mid = (front + back) / 2;
        if (mid == front)
            return;
        mergeSort(list, front, mid);
        mergeSort(list, front, back);
        merge(list, front, back);
    }

    private static void merge(Comparable[] list, int front, int back)  //O(N)
    {
        Comparable[] temp = new Comparable[back - front];

        int i = front;
        int j = (front + back) / 2;
        int k = 0;
        int mid = j;

        while (i < mid && j < back)
        {
            if (list[i].compareTo(list[j]) < 0)
            {
                temp[k] = list[i];
                k++; i++;
            }
            else
            {
                temp[k] = list[j];
                k++; i++;
            }

            while(i < mid)
            {
                temp[k++] = list[i++];
            }

            while (j < back)
            {
                temp[k++] = list[j++];
            }

            for (i = 0; i < back - front; ++i)
            {
                list[front + i] = temp[i];
            }

            out.println("pass " + passCount++ + " " + Arrays.toString(list) + "\n");
        }
    }
}

My runner:

public class MergeSortRunner
{
    public static void main(String args[])
    {
        MergeSort.mergeSort(new Comparable[]{ 9, 5, 3, 2 });
        System.out.println("\n");

        MergeSort.mergeSort(new Comparable[]{ 19, 52, 3, 2, 7, 21 });
        System.out.println("\n");

        MergeSort.mergeSort(new Comparable[]{ 68, 66, 11, 2, 42, 31});
        System.out.println("\n");
    }
}

Answer 1

I know that this is really really late, but I have the correct answer you are looking for!

import static java.lang.System.*;
import java.util.Arrays;        

public class MergeSort{

private static int passCount;

public static void mergeSort(int[] list)
{
    passCount=0;
    mergeSort(list, 0, list.length);
}

private static void mergeSort(int[] list, int front, int back)  //O( Log N )
{
    int mid = (front+back)/2;
    if(mid==front) return;
    mergeSort(list, front, mid);
    mergeSort(list, mid, back);
    merge(list, front, back);

}

private static void merge(int[] list, int front, int back)  //O(N)
{
   int dif = back-front;
   int[] temp = new int[dif];
   int beg = front, mid = (front+back)/2;
   int saveMid = mid;
   int spot = 0;

   while(beg < saveMid && mid < back) {
      if(list[beg] < list[mid]) {
         temp[spot++] = list[beg++];
      } else {
         temp[spot++] = list[mid++];
      }
   }
   while(beg < saveMid)
      temp[spot++] = list[beg++];
   while(mid < back)
      temp[spot++] = list[mid++];
   for(int i = 0; i < back-front; i++) {
      list[front+i] = temp[i];
   }
    System.out.println("pass " + passCount++ + " " + Arrays.toString(list) + "\n");
  }
 }

Here is the runner:

    public class MergeSortRunner {
    public static void main(String[] args) {
    MergeSort.mergeSort(new int[]{9,5,3,2});
    System.out.println();

    MergeSort.mergeSort(new int[]{19,52,3,2,7,21});
    System.out.println();

    MergeSort.mergeSort(new int[]{68,66,11,2,42,31});
    System.out.println();
   }
}

As it turns out, using while loops to loop through the list can help you return the proper values!

Answer 2

You need to change:

mergeSort(list, front, back);

To:

mergeSort(list, mid, back);

It's going to result in an infinite call to mergeSort because you don't change any of the input parameters between calls.

You will also probably want to change:

if(mid==front) return;

to:

if(back - front <= 1) return;

Also, your implementation choice for this algorithm is likely going to result in a non-stable sort, since you are modifying the list in place. A better option would be to have mergeSort return a list of whatever it is you're sorting, and then implement merge to take two lists as arguments, and then produce a single, merged list.

Answer 3

Try to change

if(mid==front) return;

To

if(back-front<=1) return;