MergeSort算法合并异常求助：数组右侧未与左侧正确合并

Hey there! Let's figure out why your MergeSort isn't fully sorting that array. The output you got ([-5, -10, 3, 22, -100, 1]) tells us the rightmost two elements never got properly merged into the rest of the sorted array—this usually points to a bug in either how you're splitting the array (divide step) or how you're combining the sorted subarrays (merge step).

Common Culprits to Check #

First, let's go over the most frequent mistakes that cause this exact issue:

• Incorrect recursive split boundaries: If you're not splitting the array down to single-element subarrays (e.g., wrong midpoint calculation, or stopping recursion too early), some elements won't get sorted.
• Merge step index errors: When combining the left and right sorted subarrays, you might be missing elements from the right half, or copying the merged result back to the wrong part of the original array.
• Wrong recursive call parameters: For example, passing mid instead of mid + 1 as the start of the right subarray, which would leave part of the array unsplit.

Correct MergeSort Implementation for Your Array #

Here's a complete, working Java implementation that will sort your array correctly. Compare it to your code to spot the differences:

public class MergeSortExample {
    public static void main(String[] args) {
        int[] arr = {3, -5, -10, 22, -100, 1};
        mergeSort(arr, 0, arr.length - 1);
        
        // Print the sorted array
        for (int num : arr) {
            System.out.print(num + " ");
        }
        // Output: -100 -10 -5 1 3 22
    }

    // Recursive method to split the array
    private static void mergeSort(int[] arr, int left, int right) {
        // Termination condition: subarray has 0 or 1 element (already sorted)
        if (left >= right) {
            return;
        }
        
        // Calculate midpoint safely (avoids integer overflow)
        int mid = left + (right - left) / 2;
        
        // Sort left half
        mergeSort(arr, left, mid);
        // Sort right half
        mergeSort(arr, mid + 1, right);
        // Merge the two sorted halves
        merge(arr, left, mid, right);
    }

    // Method to merge two sorted subarrays
    private static void merge(int[] arr, int left, int mid, int right) {
        // Create temporary array to hold merged elements
        int[] temp = new int[right - left + 1];
        int i = left;      // Pointer for left subarray
        int j = mid + 1;   // Pointer for right subarray
        int k = 0;         // Pointer for temp array

        // Merge elements from both subarrays in order
        while (i <= mid && j <= right) {
            if (arr[i] <= arr[j]) {
                temp[k] = arr[i];
                i++;
            } else {
                temp[k] = arr[j];
                j++;
            }
            k++;
        }

        // Add remaining elements from left subarray (if any)
        while (i <= mid) {
            temp[k] = arr[i];
            i++;
            k++;
        }

        // Add remaining elements from right subarray (if any)
        while (j <= right) {
            temp[k] = arr[j];
            j++;
            k++;
        }

        // Copy merged elements back to original array
        for (k = 0; k < temp.length; k++) {
            arr[left + k] = temp[k];
        }
    }
}

Key Fixes to Look For in Your Code #

1. Recursion Termination: Make sure you stop recursing when left >= right—this ensures you split down to single-element subarrays.
2. Midpoint Calculation: Using left + (right - left)/2 is safer than (left + right)/2 (prevents overflow for large arrays), but even the latter works for small arrays like yours. The critical part is splitting into [left, mid] and [mid+1, right].
3. Merge Step: Double-check that you're:
   • Iterating through both subarrays completely (the two while loops after the main merge loop catch remaining elements).
   • Copying the entire temp array back to the original array's correct range (arr[left + k] instead of starting at index 0).

If you share your full mergeSort and merge methods, we can pinpoint the exact line causing the issue, but comparing to the code above should help you spot the bug!

内容的提问来源于stack exchange，提问作者Mary.Math