Программа сортировки слияния всегда работает, но иногда говорит прерывание ловушки в конце

Question

Я начинающий программист на C++, только начинающий узнавать об алгоритмах/структурах данных и следую за книгой, чтобы написать программу сортировки слиянием. После преобразования внутренних массивов книги в 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 

Я гугл «Прервать ловушку: 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

При копировании результатов слияния с темпом пространства обратно к основному пространству, иногда доступ за пределы ваших векторов. Обратите внимание:

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.

Даже если это не привело к ошибкам памяти, это просто удача, что она не повредит ваши данные. Это, по-видимому, связано с тем, что вы сначала берете левую половину каждого раздела, так что всякий раз, когда у вас есть переполнение этого типа, которое фактически является границей для общего вектора, значение, уже присутствующее в временном пространстве, равно единице возникающие из предыдущего слияния, при этом копирование его в соответствующее положение в основном пространстве не влияет.

Answer 2

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

Проблема заключается в коде выше segment.It должен работать до size-1