C++指针算术实现归并排序多次运行后出现段错误求助

嘿，我太懂盯着一段代码好几天找不到bug的憋屈感了——归并排序里想用指针算术划分区间、少用临时数组的思路本身没问题，但很容易在细节上踩坑！先帮你理清楚当前代码的潜在问题，再给你调整后的可行实现。

首先先把你提供的代码片段贴出来，方便分析：

template <typename T> 
void sorts<T>::merge(T* a1, T* a2, int size1, int size2) { 
    //create buffer array 
    T* temp = new T[size1+size2]; 
    int x = 0;//index a1 
    int y = 0;//index a2 
    int z = 0;//index buffer 
    //merge int...
}

你的代码可能存在的核心问题 #

• 偏离了“指针算术划分”的初衷：你当前的merge函数接收两个独立的数组指针a1和a2，但如果是用指针算术划分原数组的子区间，merge函数应该接收的是原数组的起始、中间、结束指针（或对应索引），通过指针偏移来区分左右子数组，而不是传入两个分开的数组。
• 临时数组的冗余与内存泄漏：每次merge都创建size1+size2的临时数组，不仅效率低，还没写delete[] temp，会造成内存泄漏。更好的方式是在归并排序入口创建一次足够大的临时数组，复用所有合并操作。
• 合并逻辑的常见遗漏：从截断的代码看，你可能没处理以下两个关键步骤：
  1. 其中一个子数组遍历完后，把另一个子数组剩余元素全部拷贝到临时数组
  2. 最后把临时数组的合并结果拷贝回原数组的对应区间（这步最容易忘，导致原数组根本没被排序）

修正后的指针算术版归并排序实现 #

下面是符合你需求的实现：用指针算术划分原数组的子区间，只创建一次临时数组，避免冗余内存操作。

1. 归并排序入口函数（创建临时数组） #

template <typename T>
void sorts<T>::mergeSort(T* arr, int size) {
    if (size <= 1) return; // 递归终止条件：单个元素无需排序
    // 只创建一次临时数组，复用所有merge操作
    T* temp = new T[size];
    mergeSortHelper(arr, temp, 0, size - 1);
    delete[] temp; // 记得释放内存，避免泄漏
}

2. 递归辅助函数（用索引/指针划分区间） #

template <typename T>
void sorts<T>::mergeSortHelper(T* arr, T* temp, int left, int right) {
    if (left >= right) return;
    // 计算中间位置，用left + (right-left)/2避免整数溢出
    int mid = left + (right - left) / 2;
    // 递归排序左右两个子数组
    mergeSortHelper(arr, temp, left, mid);
    mergeSortHelper(arr, temp, mid + 1, right);
    // 合并两个已排序的子数组
    merge(arr, temp, left, mid, right);
}

3. 合并函数（用指针算术访问子数组） #

template <typename T>
void sorts<T>::merge(T* arr, T* temp, int left, int mid, int right) {
    // 用指针算术定位左右子数组的起始位置
    T* leftSubArr = arr + left;
    T* rightSubArr = arr + mid + 1;
    int leftSize = mid - left + 1;
    int rightSize = right - mid;

    int i = 0; // 左子数组的遍历索引
    int j = 0; // 右子数组的遍历索引
    int k = left; // 原数组中要写入的起始位置

    // 按顺序合并两个子数组到临时数组
    while (i < leftSize && j < rightSize) {
        // 用<=保证排序的稳定性（相同元素的相对位置不变）
        if (*(leftSubArr + i) <= *(rightSubArr + j)) {
            temp[k] = *(leftSubArr + i);
            i++;
        } else {
            temp[k] = *(rightSubArr + j);
            j++;
        }
        k++;
    }

    // 处理左子数组剩余的元素
    while (i < leftSize) {
        temp[k] = *(leftSubArr + i);
        i++;
        k++;
    }

    // 处理右子数组剩余的元素
    while (j < rightSize) {
        temp[k] = *(rightSubArr + j);
        j++;
        k++;
    }

    // 把临时数组的合并结果拷贝回原数组的对应区间
    for (int idx = left; idx <= right; idx++) {
        arr[idx] = temp[idx];
    }
}

关键细节说明 #

• 指针算术的应用：arr + left就是原数组中左子数组的起始指针，通过leftSubArr + i可以直接访问左子数组的第i个元素，这就是你想要的“用指针算术划分子数组”的核心逻辑。
• 临时数组复用：只在入口创建一次临时数组，避免了每次merge都申请内存的开销，也减少了内存泄漏的风险。
• 边界处理：注意右子数组的起始是mid + 1，不要写成mid，否则会重复处理中间元素；合并时一定要处理剩余元素，否则会丢失数据。
• 稳定性保证：比较时用<=而不是<，可以保证相同元素的相对位置不变，让排序是稳定的。

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