Stackoverflow error on generic comparable merge sort algorithm

Question

I keep getting a stackoverflow error on my mergesort call in my sort method. Its probably a quick fix, but I can't think of anything at the moment. Please look over my code.

public class MergeSorter {

    public static <T> void sort(Comparable<? extends T>[] items) {
        if (items == null) {
            throw new IllegalArgumentException("Item is null.");
        }
        mergeSort(items, 0, items.length - 1);
    }

    @SuppressWarnings("unchecked")
    private static <T> void mergeSort(Comparable<? extends T>[] items, int begIndx, int endIndx) {
        if(begIndx == endIndx) {
            return;
        }
        if(items.length > 1) {
            int midIndx = items.length / 2;
            mergeSort(items, begIndx, midIndx);
            mergeSort(items, midIndx + 1, endIndx);
            merge(items, begIndx, midIndx, endIndx);
        }
    }

    @SuppressWarnings("unchecked")
    private static <T> void merge(Comparable<? extends T>[] array, int begIndx, int midIndx, int endIndx) {
        int sizeOfLeft = midIndx - begIndx + 1;
        int sizeOfRight = endIndx - midIndx;

        /// change to generic later
        @SuppressWarnings("unchecked")
        T[] leftArr = (T[]) new Object[sizeOfLeft + 1];
        @SuppressWarnings("unchecked")
        T[] rightArr = (T[]) new Object[sizeOfRight + 1];

        for (int i = 0; i <= sizeOfLeft; i++) {
            leftArr[i] = (T) array[begIndx + i];
        }
        for (int j = 0; j <= sizeOfRight; j++) {
            rightArr[j] = (T) array[midIndx + j + 1];
        }
        int i = 0;
        int j = 0;
        for (int k = begIndx; k <= endIndx; k++) {
            if (i == sizeOfLeft) {
                array[k] = (Comparable<? extends T>) rightArr[j++];
            } else if(j == sizeOfRight) {
                array[k] = (Comparable<? extends T>) leftArr[i++];
            } else if(((Integer) leftArr[i]).compareTo((Integer)rightArr[j]) <= 0) {
                array[k] = (Comparable<? extends T>) leftArr[i++];
            } else {
                array[k]=(Comparable<? extends T>) rightArr[j++];
            }
        }
    }

}

If I give it an Integer array of 5 things
5, 24, 79, 8, 3;

Then I should get 3,5,8,24,79 back.

John Humphreys · Accepted Answer · 2019-05-26 00:10:17Z

1

Your problem is you always base your mid-index on items.length, which will be the same every call.

The mid index should be half way between your begIndx and endIndx for that call, that's what matters.

answered May 26, 2019 at 0:10

John Humphreys

39.7k44 gold badges167 silver badges262 bronze badges

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

1 Comment

John Humphreys Over a year ago

int midIndx = (begIndx + endIndx) / 2;

Collectives™ on Stack Overflow

Stackoverflow error on generic comparable merge sort algorithm

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related