归并排序C++代码出现Segmentation fault错误排查求助

Alright, let's tackle that segmentation fault you're facing—since you fixed the input issue by switching to push_back but still hit the error in the merge function, we can focus on the most common culprits in merge sort logic that cause memory access errors.

Common Causes & Fixes #

1. Out-of-Bounds Indexing in the Merge Function #

This is the #1 reason for segmentation faults in merge sort. When handling the left and right subarrays, it's easy to miscalculate indices and access memory outside the bounds of your vector or temporary arrays.

For example, if your merge function uses C-style temporary arrays (like int left[n1]) and you accidentally loop past the array length (e.g., i <= n1 instead of i < n1), you'll trigger a segfault. Similarly, if you don't initialize temporary vectors properly before using bracket notation:

// Wrong: Accessing empty vector with []
vector<int> left;
for (int i = 0; i < n1; i++)
    left[i] = arr[l + i]; 

// Right: Initialize vector with correct size first
vector<int> left(n1);
for (int i = 0; i < n1; i++)
    left[i] = arr[l + i];

2. Incorrect Recursive Call Bounds #

A tiny mistake in your mergeSort recursive calls can throw off the entire subarray range, leading to invalid memory access in the merge step.

For example, if you mistakenly call:

mergeSort(arr, l, mid - 1); // Wrong: Left subarray should go up to mid

Instead of:

mergeSort(arr, l, mid); // Correct: Left range is l to mid
mergeSort(arr, mid + 1, r); // Correct: Right range is mid+1 to r

Also, calculate mid safely to avoid integer overflow (critical for large arrays):

int mid = l + (r - l) / 2; // Better than (l + r) / 2

3. Uninitialized or Mis-sized Temporary Storage #

If you're using dynamic memory allocation (like new int[n1]) in the merge function and forget to deallocate it, or if you allocate the wrong size, you'll run into memory issues. Stick to vector for temporary storage—it handles sizing and cleanup automatically, reducing this risk.

Debugging Tips #

• Add print statements in the merge function to output values of l, mid, r, n1, and n2—this will help you spot if any of these values are unexpected (e.g., negative numbers or values larger than your vector's size).
• Use a debugger like GDB to step through your code and see exactly which line triggers the segfault. This is the fastest way to pinpoint the exact memory access error.

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