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.

Answer 1

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