0

I'm writing a merge sort class in java and i get a stack overflow error when I get to the sort(left) line. Any thoughts? I don't understand why this would be a problem.

package ds;

import java.util.Comparator;

public class MergeSorter<T> extends Sorter<T> {

public MergeSorter(Comparator<T> comparator){
    super(comparator);
}

@SuppressWarnings("unchecked")
@Override
public void sort(T[] array){
    if (array.length <= 1);
    else {
        T[] left = (T[]) new Object[array.length/2 + 1];
        T[] right = (T[]) new Object[array.length/2 + 1];
        int middleIndex = array.length / 2;
        for (int i = 0; i < middleIndex; i++) {
            left[i] = array[i];
        }
        for (int i = middleIndex; i < array.length; i++) {
            right[i - middleIndex] = array[i];
        }
        sort(left);
        sort (right);
        merge(left, right, array);
    }
}

public final void merge(T[] left, T[] right, T[] array){
    Array<T> sortedArray = new Array<T>(array.length);
    while (left.length > 0 || right.length > 0) {
        if (left.length > 0 && right.length > 0) {
            if (comparator.compare(left[0], right[0]) < 0) {
                sortedArray.add(left[0]);
                for (int i = 1; i < left.length; i++) {
                    left[i - 1] = left[i];
                    left[left.length - 1] = null;
                }
            }
            else {
                sortedArray.add(right[0]);
                for (int i = 1; i < right.length; i++) {
                    right[i - 1] = right[i];
                    right[right.length - 1] = null;
                }
            }
        }
        else if (left.length > 0) {
            sortedArray.add(left[0]);
            for (int i = 1; i < left.length; i++) {
                left[i - 1] = left[i];
                left[left.length - 1] = null;
            }
        }
        else if (right.length > 0) {
            sortedArray.add(right[0]);
            for (int i = 1; i < right.length; i++) {
                right[i - 1] = right[i];
                right[right.length - 1] = null;
            }
        }
    }
    for (int i = 0; i < array.length; i++) {
        array[i] = sortedArray.get(i);
    }
}

}
Improve this question

1 Answer 1

Reset to default
1

Suppose the array has length 2. Then left is:

T[] left = (T[]) new Object[array.length/2 + 1];

which is

T[] left = (T[]) new Object[2/2 + 1];

and this equals to

T[] left = (T[]) new Object[2];

And when you sort on left, this continues, and leads to an infinite recursion which might have caused the stack overflow error you posted.

Since you are copying the first middleIndex elements into left, middleIndex length should right fit the array left. So left should be a length array.length/2 array.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

Are you sure? Doesn't array.length count the number of elements in the array, not the actual capacity of the array? So even if the array is not full, array.length would still be good in the recursion, if i'm not mistaken. The reason I did this was to account for odd-sized arrays.
Array.length just return a fixed number, the array's length. I do not really get what you mean, but [null, null] has length 2.
You only want to add 1 to either the left or right. Integer division will round down then you need to decide where the 1 goes.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.