Issue with merge sort Algorithm

Question

MergeSorting algorithm not working. Keep getting an IndexOutOFBoundsError. I believe the issue may be because there isn't a sentinel. I need to create a loop when the leftarray and rightarray is copying itself to k, one of the arrays runs out of numbers, which causes an error. I need some assistance creating this sentinel.

private static <T> void mergeSort(Comparable<? extends T>[] items, int begIndx, int endIndx) {
    if (items.length > 1) {
        int midIndx = items.length / 2;
        @SuppressWarnings("unchecked")
        T[] left = (T[]) new Object[midIndx];
        @SuppressWarnings("unchecked")
        T[] right = (T[]) new Object[items.length - midIndx];

        for (int i = 0; i < midIndx; i++) {
            left[i] = (T) items[i];
        }
        for (int i = midIndx; i < items.length; i++) {
            right[i] = (T) items[i];
        }

        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;

    // changed to less than or equal to rather than "less than"
    // this is because this is a zero based index system
    // and because endeIndex is not a length but an index,
    // you need to populate it.
    for (int k = begIndx; k <= endIndx; k++) {
        // use comparable here
        if (((Integer) leftArr[i]).compareTo((Integer) rightArr[j]) <= 0) {
            array[k] = (Comparable<? extends T>) leftArr[i];
            i = i + 1;
        } else if (((Integer) leftArr[i]).compareTo((Integer) rightArr[j]) >= 0) {
            /// just replaces it so don't use comparable
            array[k] = (Comparable<? extends T>) rightArr[j];
            j = j + 1;
        } else if ((Integer) leftArr[sizeOfLeft] == null) {
            array[k] =  (Comparable<? extends T>) rightArr[j];
            j = j + 1;
        } else if ((Integer) rightArr[sizeOfRight] == null) {
            array[k] = (Comparable<? extends T>) leftArr[i];
            i = i + 1;
        }
    }
}

I created an integer array arr = new Integer[5]. So those 5 numbers should be sorted.

Please define "not working". Do you get an error? Not correct output? — GBlodgett
– GBlodgett, Commented May 25, 2019 at 19:57
At least one of your problems is that - in the first method - you access the right array with the range [midRange, items.length] while your right array has an index [0, items.length - midRange]. — second
– second, Commented May 25, 2019 at 21:10
Your loop for the right array is wrongly defined. You're trying to assign to index right[midIndx] to begin with while you should be assigning to right[i - midIndx] but this is unfortunately not the only problem — Yassin Hajaj
– Yassin Hajaj, Commented May 26, 2019 at 16:53

chqrlie · Accepted Answer · 2019-05-26 20:51:17Z

There are multiple problems in your code:

it is unclear if the index endIndx is included or excluded. The code is much simpler if the endIndx is excluded, and the initial call to sort the array is simply: mergesort(arr, 0, arr.length);
the initial test in mergesort is incorrect: instead of testing the array length, you should test if the slice has more than 1 element:
```
if (endIndx - begIndx > 1)
```
the arrays left and right are unused in mergesort.
allocating an extra element in the arrays left and right in merge is not required, it is much simpler to compare the array index values against the lengths of the subarrays. This sentinel approach is confusing and should not be used.

Here is a simplified version:

private static <T> void mergeSort(Comparable<? extends T>[] items, int begIndx, int endIndx) {
    if (endIndx - begIndx > 1) {
        int midIndx = items.length / 2;
        mergeSort(items, begIndx, midIndx);
        mergeSort(items, midIndx, 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;
    int sizeOfRight = endIndx - midIndx;

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

    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];
    }

    int i = 0;
    int j = 0;
    int k = begIndx;

    while (i < sizeOfLeft && j < sizeOfRight) {
        /// use comparable to compare actual values
        if ((Integer)leftArr[i]).compareTo((Integer)rightArr[j]) <= 0) {
            array[k] = (Comparable<? extends T>)leftArr[i];
            i++;
            k++;
        } else {
            array[k] = (Comparable<? extends T>)rightArr[j];
            j++;
            k++;
        }
    }
    while (i < sizeOfLeft) {
        array[k] = (Comparable<? extends T>)leftArr[i];
        i++;
        k++;
    }
    while (j < sizeOfRight) {
        array[k] = (Comparable<? extends T>)rightArr[j];
        j++;
        k++;
    }
}

Collectives™ on Stack Overflow

Issue with merge sort Algorithm

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related