CODEWITHSUNDEEP
javaalgorithmsortingstack-overflowmergesort
InquisitiveCoder
InquisitiveCoder

Reputation: 45

Stackoverflow error on generic comparable merge sort algorithm

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.

Upvotes: 1

Views: 86

Answers (1)

John Humphreys
John Humphreys

Reputation: 39324

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.

Upvotes: 1

Related Questions