归并排序算法出现IndexOutOfBoundsException问题求助及泛型改造需求

First up, let's squash that ArrayIndexOutOfBoundsException you're hitting. Looking at your stack trace and code, there are a few clear issues causing the error—then we'll tackle the generic version.

1. Fixing the Index Error #

Let's walk through the bugs in your merge method step by step:

a. Sentinel Value Index Mismatch #

You initialized leftArr with length sizeOfLeft + 1, which means its valid indices go from 0 to sizeOfLeft (Java arrays are 0-indexed). But you tried assigning the sentinel value to leftArr[sizeOfLeft + 1]—that's one index past the array's end, hence the out-of-bounds error. Same goes for rightArr.

Fix this by assigning the sentinel to the last valid index of each array:

leftArr[sizeOfLeft] = Integer.MAX_VALUE;
rightArr[sizeOfRight] = Integer.MAX_VALUE;

b. Incomplete Merge Loop #

Your final merge loop runs for(int k = begIndx; k < endIndx; k++)—this stops before endIndx, leaving the last element of the target range unprocessed. Change the condition to include endIndx:

for(int k = begIndx; k <= endIndx; k++)

c. (Optional but Recommended) Switch to 0-Indexed Arrays #

Your code uses 1-indexed loops for leftArr and rightArr, which is counterintuitive in Java and easy to mess up. Here's the safer, more idiomatic 0-based approach:

for(int i = 0; i < sizeOfLeft; i++) {
    leftArr[i] = array[begIndx + i];
}
for(int j = 0; j < sizeOfRight; j++) {
    rightArr[j] = array[midIndx + 1 + j];
}
// Initialize i and j to 0 instead of 1
int i = 0;
int j = 0;

Fixed Non-Generic MergeSorter #

Putting it all together, here's the corrected int version:

public class MergeSorter {
    public static void sort(int[] array, int begIndx, int endIndx) {
        if (array == null) {
            throw new IllegalArgumentException("Item is null.");
        }
        if(begIndx < endIndx) {
            int midIndx = (begIndx + endIndx) / 2; // Integer division handles floor automatically
            sort(array, begIndx, midIndx);
            sort(array, midIndx + 1, endIndx);
            merge(array, begIndx, midIndx, endIndx);
        }
    }

    public static void merge(int[] array, int begIndx, int midIndx, int endIndx) {
        int sizeOfLeft = midIndx - begIndx + 1;
        int sizeOfRight = endIndx - midIndx;

        int[] leftArr = new int[sizeOfLeft + 1];
        int[] rightArr = new int[sizeOfRight + 1];

        // 0-indexed population loops
        for(int i = 0; i < sizeOfLeft; i++) {
            leftArr[i] = array[begIndx + i];
        }
        for(int j = 0; j < sizeOfRight; j++) {
            rightArr[j] = array[midIndx + 1 + j];
        }

        // Sentinel values at valid last indices
        leftArr[sizeOfLeft] = Integer.MAX_VALUE;
        rightArr[sizeOfRight] = Integer.MAX_VALUE;

        int i = 0;
        int j = 0;
        // Include endIndx to process all elements
        for(int k = begIndx; k <= endIndx; k++) {
            if(leftArr[i] <= rightArr[j]) {
                array[k] = leftArr[i];
                i++;
            } else {
                array[k] = rightArr[j];
                j++;
            }
        }
    }
}

2. Converting to a Generic Version #

To make this work with any comparable type, we'll adjust the code to use generics with Comparable<T> bounds. We'll also ditch the Integer.MAX_VALUE sentinel (since not all types have a "max value" field) and use explicit checks for remaining elements instead:

Generic MergeSorter Implementation #

public class GenericMergeSorter {
    // Generic sort method with Comparable bound to enable element comparison
    public static <T extends Comparable<T>> void sort(T[] array, int begIndx, int endIndx) {
        if (array == null) {
            throw new IllegalArgumentException("Array is null.");
        }
        if(begIndx < endIndx) {
            int midIndx = (begIndx + endIndx) / 2;
            sort(array, begIndx, midIndx);
            sort(array, midIndx + 1, endIndx);
            merge(array, begIndx, midIndx, endIndx);
        }
    }

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

        // Create generic arrays (unchecked cast is necessary here)
        @SuppressWarnings("unchecked")
        T[] leftArr = (T[]) new Comparable[sizeOfLeft];
        @SuppressWarnings("unchecked")
        T[] rightArr = (T[]) new Comparable[sizeOfRight];

        // Populate left and right subarrays
        for(int i = 0; i < sizeOfLeft; i++) {
            leftArr[i] = array[begIndx + i];
        }
        for(int j = 0; j < sizeOfRight; j++) {
            rightArr[j] = array[midIndx + 1 + j];
        }

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

        // Merge elements while both subarrays have remaining items
        while (i < sizeOfLeft && j < sizeOfRight) {
            if(leftArr[i].compareTo(rightArr[j]) <= 0) {
                array[k] = leftArr[i];
                i++;
            } else {
                array[k] = rightArr[j];
                j++;
            }
            k++;
        }

        // Copy remaining elements from left subarray (if any)
        while (i < sizeOfLeft) {
            array[k] = leftArr[i];
            i++;
            k++;
        }

        // Copy remaining elements from right subarray (if any)
        while (j < sizeOfRight) {
            array[k] = rightArr[j];
            j++;
            k++;
        }
    }
}

Key Generic Changes: #

• Added a type parameter <T extends Comparable<T>> to ensure the type can be compared.
• Replaced int[] with T[] across the codebase.
• Swapped direct <= comparisons with compareTo(), the standard way to compare comparable objects.
• Removed sentinel values and used while loops to handle remaining elements once one subarray is exhausted.

内容的提问来源于stack exchange，提问作者InquisitiveCoder