归并排序（MergeSort）算法实现异常求助

Hey there! Let's work through your MergeSort issue. You mentioned your code is running abnormally, but only shared the start of your mergeSort method—full code would let us pinpoint the exact bug, but let's go over the most common mistakes that trip up MergeSort implementations, especially since you're using Java's int... varargs.

Common MergeSort Pitfalls to Check #

• Incorrect Recursive Base Case
  You said your code recurses down to single-element lists, but double-check your base condition. It should stop when the subarray has 0 or 1 elements. A common mistake is using low > high instead of low >= high, which can lead to unnecessary recursive calls or missed edge cases:

  // Correct base case
  if (low >= high) {
      return;
  }
  

• Merge Step Errors
  This is where most bugs happen! Watch for these:

  • Wrong temp array size: The temporary array should only be the size of the current subarray (high - low + 1), not the entire original array.
  • Pointer out-of-bounds: When merging, once the left subarray pointer (i) passes mid or the right pointer (j) passes high, you need to copy the remaining elements directly instead of continuing comparisons.
  • Misaligned indices when copying back: When moving elements from the temp array to the original, start at low (not index 0) to target the correct subarray position.

• Varargs & Recursive Range Handling
  Using int... means you'll need to track the current subarray's low and high indices in recursive calls. Don't pass the entire array every time—instead, split it into subranges. A typical structure looks like this:

  // Public method to start sorting
  public void mergeSort(int... arr) {
      if (arr == null || arr.length <= 1) return;
      mergeSort(arr, 0, arr.length - 1);
  }
  
  // Private recursive helper with range indices
  private void mergeSort(int[] arr, int low, int high) {
      if (low >= high) return;
      // Calculate mid safely to avoid integer overflow
      int mid = low + (high - low) / 2;
      mergeSort(arr, low, mid);
      mergeSort(arr, mid + 1, high);
      merge(arr, low, mid, high);
  }
  

• Integer Overflow in Mid Calculation
  Avoid using (low + high) / 2 to find the midpoint—when low and high are large, this can overflow the int range. Use low + (high - low) / 2 instead, which gives the same result without overflow.

Example Correct Merge Method #

Here's a solid implementation of the merge step to reference:

private void merge(int[] arr, int low, int mid, int high) {
    int[] temp = new int[high - low + 1];
    int leftPtr = low;
    int rightPtr = mid + 1;
    int tempPtr = 0;

    // Merge elements into temp array
    while (leftPtr <= mid && rightPtr <= high) {
        if (arr[leftPtr] <= arr[rightPtr]) {
            temp[tempPtr++] = arr[leftPtr++];
        } else {
            temp[tempPtr++] = arr[rightPtr++];
        }
    }

    // Copy remaining left subarray elements
    while (leftPtr <= mid) {
        temp[tempPtr++] = arr[leftPtr++];
    }

    // Copy remaining right subarray elements
    while (rightPtr <= high) {
        temp[tempPtr++] = arr[rightPtr++];
    }

    // Move sorted temp array back to original array
    for (tempPtr = 0; tempPtr < temp.length; tempPtr++) {
        arr[low + tempPtr] = temp[tempPtr];
    }
}

If you can share your full mergeSort and merge code, we can spot exactly where things are going wrong!

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