归并排序中使用(right-left)/2为何会引发Segmentation Fault？

问题背景 #

我了解到使用left + (right - left) / 2而非(left + right) / 2可以避免整数溢出，但好奇为什么把归并排序里的mid计算改成(right - left) / 2会触发Segmentation Fault，以及这个错误在代码里埋下的隐患具体在哪里。

错误的归并排序核心代码：

void mergesort(int arr[], int left , int right){
    if (left<right){
        int mid = (right - left) / 2; // 将此处改为(right-left)/2后引发段错误！
        mergesort(arr, left, mid);
        mergesort(arr, mid + 1, right);

        merge(arr, left, mid, right);
    }
}

完整代码：

#include <stdio.h>

void merge(int arr[], int start, int middle, int end){
    // 计算子数组大小
    int left_size = middle - start + 1;
    int right_size = end - middle;
    int left[left_size]; int right[right_size];
    
    // 复制元素到子数组
    for (int i=0; i < left_size; i++){
        left[i] = arr[start + i];
    }
    for (int i=0; i < right_size; i++){
        right[i] = arr[middle + i + 1];
    }

    // 数组指针
    int lp,rp, ap;
    lp = 0;
    rp = 0;
    ap = start;

    while (lp < left_size && rp < right_size){
        if (left[lp] <= right[rp]){
            arr[ap] = left[lp];
            lp++;
        }
        else{
           arr[ap] = right[rp];
           rp++;
        }
        ap++;
    }

    while (lp < left_size){
        arr[ap] = left[lp];
        lp++; 
        ap++;
    }
    while (rp < right_size){
        arr[ap] = right[rp];
        rp++; ap++;
    }
};

void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main() {
    int arr[] = {6, 5, 12, 10, 9, 1};
    int size = sizeof(arr) / sizeof(arr[0]);

    mergesort(arr, 0, size - 1);

    printf("Sorted array: \n");
    printArray(arr, size);
}

错误引发段错误的核心原因 #

1. 递归陷入无限循环，耗尽栈空间 #

(right - left)/2计算的是当前区间长度的一半，而非原数组中的绝对中间索引。举个具体例子：

• 初始调用mergesort(arr, 0, 5)（数组长度6），计算得mid=(5-0)/2=2，此时递归调用mergesort(arr,3,5)处理右半区间。
• 在mergesort(arr,3,5)中，mid=(5-3)/2=1，接下来会调用mergesort(arr,3,1)（因left>right直接返回），然后调用mergesort(arr,2,5)。
• 在mergesort(arr,2,5)中，mid=(5-2)/2=1，再次调用mergesort(arr,2,1)返回，接着又调用mergesort(arr,2,5)——陷入无限递归。

不断的递归调用会耗尽程序的栈内存，最终触发Segmentation Fault（栈溢出）。

2. merge函数触发非法内存访问 #

错误的mid值会导致merge函数的参数middle完全偏离正确区间，引发两种内存问题：

• 变长数组长度异常：比如当start=2、middle=1时，left_size=1-2+1=0，定义长度为0的变长数组left[0]属于C标准中的未定义行为，可能直接触发内存访问错误。
• 数组越界访问：错误的middle会让arr[middle + i +1]访问到数组范围外的内存（比如索引为负数或超过数组最大下标），触发非法内存访问，直接导致Segmentation Fault。

正确的mid计算逻辑 #

mid = left + (right - left)/2的作用是计算[left, right]区间的绝对中间索引：

• right - left得到当前区间的长度，除以2得到半长，加上left后，确保mid始终落在[left, right]范围内，递归能正确划分区间并最终收敛终止，同时避免了(left+right)/2可能出现的整数溢出问题。

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