合并排序程序总是有效，但有时会在最后说 abort trap

Question

我是一名初学 C++ 的程序员，刚开始学习 algorithms/data 结构，并且正在阅读一本书来编写归并排序程序。将书中的 int 数组转换为 int 向量后，排序似乎仍然有效，但偶尔会在最后吐出错误。我似乎无法弄清楚为什么这种情况有时会发生。这就是它所说的：

mergesort_sa(36921,0x7fff74240000) malloc: *** error for object 0x7f879a500118: incorrect checksum for freed object - object was probably modified after being freed.
*** set a breakpoint in malloc_error_break to debug
Abort trap: 6

我用谷歌搜索 "Abort trap: 6"，它说了一些关于写入我不拥有的内存的内容。我查看了我的程序，我认为我传递的左右边界是正确的，所以我不明白为什么要这样说。任何人都知道为什么会这样或者能够告诉我为什么它只是偶尔发生而不是每个运行？这是我的完整代码：

#include <iostream>
#include <vector>
using namespace std;

void merge(vector<int> &numbers, vector<int> &temp_numbers, int left, int mid, int right);
int l = 0, r = 0, m = 0;

void merge_sort(vector<int> &numbers, vector<int> &temp_numbers, int left, int right){     
    int mid;    

    if (right > left) {
        mid = (left+right)/2;
        cout << "LEFT SORT" << endl;
        l++;
        merge_sort(numbers, temp_numbers, left, mid);   
        cout << "RIGHT SORT"  << endl;
        r++;
        merge_sort(numbers, temp_numbers, mid+1, right); 
        cout << "MERGE" << endl;
        m++;
        merge(numbers, temp_numbers, left, mid+1, right);   
    }
}

void merge(vector<int> &numbers, vector<int> &temp_numbers, int left, int mid, int right){
    int i, left_end, size, temp_pos;
    left_end = mid - 1;
    temp_pos = left;
    size = right-left + 1;

    while ((left <= left_end) && (mid <= right)) {
        if (numbers[left] <= numbers[mid]) {
            temp_numbers[temp_pos] = numbers[left];
            temp_pos++;
            left++;
        }   
        else {
            temp_numbers[temp_pos] = numbers[mid];
            temp_pos++;
            mid++;
        }
    }
    while (left <= left_end) {
        temp_numbers[temp_pos] = numbers[left];
        left++;
        temp_pos++;
    }
    while (mid <= right) {
        temp_numbers[temp_pos] = numbers[mid];
        mid++;
        temp_pos++;
    }
    for (i = 0; i <= size; i++) {
        numbers[right] = temp_numbers[right];
        right--;
    }
}

int main(int argc, char *argv[]) {

    vector<int> numbers, temp_numbers;
    int x, n;

    // setup
    cout << "Enter numbers to sort separated by spaces. Press Ctrl+D when you are finished.\n\n";
    while(cin >> x) {
        numbers.push_back(x);
    }
    n = numbers.size();
    temp_numbers.resize(n);
    cout << "\nCount: " << n << endl << "Numbers to be sorted: ";
    for (int i = 0; i < n; i++)
        cout << numbers[i] << " ";
    cout << endl << endl << "Steps taken:\n";

    // sort
    merge_sort(numbers, temp_numbers, 0, n-1);

    // print
    cout << endl << "Sorted array: ";
    for (int i = 0; i < n; i++)
        cout << numbers[i] << " ";
    cout << endl << endl << "left sorts: " << l << "  right sorts: " << r << "  merges: " << m << endl; 
    return 0;
}

Answer 1

当您将合并结果从临时 space 复制回主 space 时，您有时会超出向量的范围。观察：

size = right-left + 1;

因为 right 和 left 索引是包含在内的，所以 size 因此保存了要合并的子数组中的元素数。但是你这样做：

for (i = 0; i <= size; i++) {
    numbers[right] = temp_numbers[right];
    right--;
}

执行 size + 1 次迭代，而您只想复制 size 元素。当 left 为 0 时，即在索引 -1 处访问向量边界外（下方）。

即使这没有产生内存错误，它也不会破坏您的数据，这完全是幸运的。这似乎是由于您首先对每个分区的左半部分进行递归，因此无论何时这种类型的溢出实际上是整个向量的边界，该值已经存在于 temp space 是前一次合并产生的，因此将其复制到主 space 中的相应位置没有任何效果。

Answer 2

 for (i = 0; i <= size; i++) {
    numbers[right] = temp_numbers[right];
    right--;
}

问题出在上面的代码segment.It应该运行直到size-1

合并排序程序总是有效，但有时会在最后说 abort trap

Merge sort program always works, but sometimes says abort trap at the end

c++

mergesort

runtime-error