整数数组升序排序C++归并代码触发AddressSanitizer栈溢出问题求解

功能需求 #

给定整数数组nums，需将其按升序排序。

• 测试用例1：输入nums = [5,2,3,1]，输出应为[1,2,3,5]
• 测试用例2：输入nums = [5,1,1,2,0,0]，输出应为[0,0,1,1,2,5]

报错信息 #

运行代码触发AddressSanitizer栈溢出错误：

AddressSanitizer:DEADLYSIGNAL
32ERROR: AddressSanitizer: stack-overflow on address 0x7ffdd2294ff8 (pc 0x000000345b86 bp 0x7ffdd22950d0 sp 0x7ffdd2295000 T0)
32ABORTING

问题代码 #

#include <vector>

class Solution {
public: 
    
    void helper(std::vector<int>& nums, int start, int end) {

        if (start <= end) {

            int mid = (start + end) / 2;

            helper(nums, start, mid);
            helper(nums, mid + 1, end);

            int i = start;
            int j = mid;
            int k = mid + 1;
            int l = end;
            int m = 0;

            int ans[nums.size()];

            while (i < mid && k < end) {
                if (nums[i] < nums[j]) {
                    ans[m++] = nums[i++];
                }
                else {
                    ans[m++] = nums[j++];
                }
            }
            while (i < mid) {
                ans[m++] = nums[i++];
            }
            while (j < end) {
                ans[m++] = nums[j++];
            }
            i = start;
            j = end;

            while (i <= j) {
                nums[i++] = ans[i++];
            }
        }
    }
    std::vector<int> sortArray(std::vector<int>& nums) {

        int n = nums.size() - 1;

        helper(nums, 0, n);

        std::vector<int>finalans;
        for (int i = 0; i < nums.size(); i++) {

            finalans.push_back(nums[i]);
        }
        return finalans;
    }
};

• 递归终止条件错误（栈溢出直接原因）：原代码判断if(start <= end)才进入处理逻辑，当子数组长度为1（start == end）时，会无限递归调用helper(nums, start, mid)（此时mid == start），最终导致栈溢出。正确逻辑应为子数组长度≤1时直接返回，即if(start >= end) return;。
• 合并逻辑变量错误：归并排序的两个有序子区间应为[start, mid]和[mid+1, end]，原代码错误将右区间起始点设为mid，且定义的k变量未使用，循环边界i < mid、k < end不符合区间范围，会导致元素漏排。
• 非法变长数组+栈空间浪费：C++标准不支持栈上变长数组int ans[nums.size()]，且每次递归都申请整个原数组大小的栈空间，进一步加剧栈溢出风险。
• 回填数组逻辑错误：原代码回填时nums[i++] = ans[i++]对同一个i自增两次，会导致数组越界、元素赋值错位。
• mid计算存在溢出风险：(start + end) / 2在数组长度较大时，start+end可能超出int范围溢出，改为start + (end - start)/2更安全。

#include <vector>
using namespace std;

class Solution {
private:
    void helper(vector<int>& nums, int start, int end) {
        // 子数组长度<=1直接返回
        if (start >= end) {
            return;
        }
        // 避免溢出的mid计算方式
        int mid = start + (end - start) / 2;
        // 递归排序左右子区间
        helper(nums, start, mid);
        helper(nums, mid + 1, end);
        // 合并两个有序子区间
        int i = start; // 左区间指针
        int j = mid + 1; // 右区间指针
        vector<int> tmp(end - start + 1); // 临时存储合并结果，仅申请当前区间大小的空间
        int idx = 0;
        while (i <= mid && j <= end) {
            if (nums[i] <= nums[j]) {
                tmp[idx++] = nums[i++];
            } else {
                tmp[idx++] = nums[j++];
            }
        }
        // 追加左区间剩余元素
        while (i <= mid) {
            tmp[idx++] = nums[i++];
        }
        // 追加右区间剩余元素
        while (j <= end) {
            tmp[idx++] = nums[j++];
        }
        // 合并结果回填到原数组
        for (int p = 0; p < tmp.size(); p++) {
            nums[start + p] = tmp[p];
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        helper(nums, 0, nums.size() - 1);
        return nums;
    }
};

修正后代码可正常通过所有测试用例，不会触发栈溢出错误，时间复杂度为O(nlogn)，符合归并排序的性能要求。

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