实现C++14归并排序时Stack Smashing Detected错误的原因与解决

错误根源 #

你的代码触发Stack Smashing Detected的核心问题在merge函数里：k的初始化值错误。

你把k初始化为high，然后每次赋值后执行k++——这意味着合并时会从res数组的末尾开始写，写完一个就往数组外面越界写（比如数组长度是8，索引最大是7，k从7开始，加1就到8，直接超出数组范围）。这种越界写操作会破坏栈上的其他数据，触发系统的栈溢出保护机制，抛出这个错误。

标准归并排序的合并逻辑里，应该从子数组的起始位置（也就是low）开始填充临时数组，而不是从末尾。

修复方案 #

只需要修改merge函数中k的初始化行：
把int i=low,j=mid+1,k=high;改成int i=low,j=mid+1,k=low;。

修正后的完整代码 #

#include<iostream>
using namespace std;

// 合并两个已排序子数组
void merge(int arr[], int res[], int low, int mid, int high) {
    // 修正k的初始值为low，从子数组起始位置开始填充临时数组
    int i=low,j=mid+1,k=low;
    while(i<=mid && j<=high) {
        if(arr[i]<=arr[j])
            res[k++]=arr[i++];
        else
            res[k++]=arr[j++];
    }
    // 拷贝左子数组剩余元素
    while(i<=mid)
       res[k++]=arr[i++];
    // 拷贝右子数组剩余元素
    while(j<=high)
        res[k++]=arr[j++];
    // 将合并结果复制回原数组
    for(i=low;i<=high;i++)
        arr[i]=res[i];
}

void mergeSort(int arr[], int res[], int low, int high) {
    if(high == low)
        return;
    int mid = low + (high-low)/2;
    mergeSort(arr,res,low,mid);
    mergeSort(arr,res,mid+1,high);
    merge(arr,res,low,mid,high);
}

int main() {
    int arr[] = {8,4,3,12,25,6,13,10};
    int res[]= {8,4,3,12,25,6,13,10};
    
    cout << "排序前：";
    for(int i=0 ;i<8 ; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    
    mergeSort(arr,res,0,7);
    
    cout << "排序后：";
    for(int i=0 ;i<8 ; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
}

效果验证 #

修改后，合并操作会在res数组的合法索引范围内写入数据，不会再触发栈溢出错误，归并排序可以正常运行，输出正确的排序结果。

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