归并排序出现Segmentation Fault:11错误，请求技术协助

Hey there! Let's troubleshoot that segmentation fault you're running into with your merge logic. The Segmentation Fault:11 almost always points to an out-of-bounds memory access, and as you suspected, the issue is indeed tied to how you're calculating and using the middle index m—specifically in how you're populating the a2 temporary array.

First, the Critical Indexing Bug #

Looking at your code for populating a2:

for (int j = 0; j < l2; j++) {
    a2[j] = n[s + m + j];
}

This is wrong. The right half of your subarray starts at index m, not s + m. The s is already the starting index of the current subarray you're working with, so adding it to m shifts way past the actual start of the right half.

For example, if you're sorting the subarray starting at s=1 (elements 3,2,1 in your test array) with m=2 and e=3, s + m would be 3—j=0 accesses n[3] (which is okay), but j=1 tries to access n[4]—outside your array bounds, triggering the segmentation fault.

Fix this by changing the line to:

a2[j] = n[m + j];

Second, Ensure Consistency in m's Meaning #

You need to make sure the way you calculate m when calling merge() matches how you use it inside the function. From your code, it looks like:

• Left subarray: [s, m-1] (length l1 = m - s)
• Right subarray: [m, e] (length l2 = e - m + 1)

When calling merge() from your merge sort function, compute the middle index safely (to avoid integer overflow) with:

int m = s + (e - s) / 2;

Stick to one convention for m's meaning—mixing definitions will lead to off-by-one errors and crashes.

Third, Guard Against Zero-Length Arrays #

Your code uses variable-length arrays (VLAs) for a1 and a2. If l1 or l2 is 0 (like when sorting a single-element subarray), creating a VLA of length 0 is undefined behavior. Add a quick check at the start of merge() to skip unnecessary work:

if (l1 <= 0 || l2 <= 0) {
    return; // No elements to merge
}

Fixed Code Snippet #

Here's your merge function with the fixes applied, plus a complete merge sort setup to test with your {4,3,2,1} array:

#include <stdio.h>

void merge(int s, int e, int m, int n[]) {
    int l1 = m - s;
    int l2 = e - m + 1;

    // Guard against invalid array lengths
    if (l1 <= 0 || l2 <= 0) {
        return;
    }

    int a1[l1];
    int a2[l2];

    // Populate left temp array
    for (int i = 0; i < l1; i++) {
        a1[i] = n[s + i];
    }

    // Fixed: Populate right temp array using correct index
    for (int j = 0; j < l2; j++) {
        a2[j] = n[m + j];
    }

    // Merge the temp arrays back into n
    int i = 0, j = 0, k = s;
    while (i < l1 && j < l2) {
        if (a1[i] <= a2[j]) {
            n[k++] = a1[i++];
        } else {
            n[k++] = a2[j++];
        }
    }

    // Copy remaining elements from a1
    while (i < l1) {
        n[k++] = a1[i++];
    }

    // Copy remaining elements from a2
    while (j < l2) {
        n[k++] = a2[j++];
    }
}

void merge_sort(int s, int e, int n[]) {
    if (s < e) {
        int m = s + (e - s) / 2; // Safe middle index calculation
        merge_sort(s, m - 1, n); // Sort left subarray [s, m-1]
        merge_sort(m, e, n);     // Sort right subarray [m, e]
        merge(s, e, m, n);       // Merge the two sorted subarrays
    }
}

int main() {
    int n[] = {4, 3, 2, 1};
    int len = sizeof(n) / sizeof(n[0]);

    merge_sort(0, len - 1, n);

    // Print sorted array
    for (int i = 0; i < len; i++) {
        printf("%d ", n[i]);
    }
    printf("\n");

    return 0;
}

This should resolve the segmentation fault and correctly sort your test array.

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