合并排序算法：std::out_of_range

Question

我目前正在制作合并排序算法，但是当我运行代码时，我收到一条错误消息：“在抛出 'std::out_of_range 的实例后终止调用”。这是我的代码。

template<typename T>
void merge(std::vector<T> &vec, int l, int m, int r){
    int i = l;
    int j = m + 1;
    int k = l;
    
    //CREATE TEMPORARY MEMORY
    int temp[vec.size()];

    while(vec.at(i) <= m && j <= r){
        if(vec.at(i) <= vec.at(j)){
            temp[k] = vec.at(i);
            i++;
            k++;
        }else{
            temp[k] = vec.at(j);
            j++;
            k++;
        }
    }
    while (i <= m){ //first half: Copy the remaining elements of first half, if there are any
        temp[k] = vec.at(i);
        i++;
        k++;
    }
    while (j <= r){ //second half: Copy the remaining elements of second half, if there are any 
        temp[k] = vec.at(j);
        j++;
        k++;
    }
    for(size_t p = 1; p <= r; p++){ //copy temp array to original array
        vec.at(p) = temp[k];
    }
}

合并排序函数

template<typename T>
void mergeSort(std::vector<T> &vec, int l, int r){
    if(l < r){ 
        int m = (l + r) / 2; //find midpoint
        mergeSort(vec, l, m); //first half
        mergeSort(vec, m + 1, r); //second half
        merge(vec, l, m, r); // merge
    }
}

Answer 1

您的 merge 函数中的一些问题（您可以通过调试轻松发现）：

vec.at(i) <= m 将 value 与 index 进行比较。这两者是无关的。所以改变：
```
while(vec.at(i) <= m && j <= r){ 
```
与：
```
while(i <= m && j <= r){ 
```
最后一个循环以 p = 1 开始，这是一个在许多情况下超出合并范围的索引。所以改变：
```
for(size_t p = 1; p <= r; p++){
```
与：
```
for(size_t p = l; p <= r; p++){
```
同一循环的主体使用 k 作为索引，但该变量与循环无关，并且具有超出正在考虑的范围的值。所以改变：
```
vec.at(p) = temp[k];
```
与：
```
vec.at(p) = temp[p];
```

通过这些更改，您的代码将正常工作。

然而，遗憾的是temp总是有完整向量的大小，而你只使用它的一小部分。考虑减少内存使用量。

合并排序算法：std::out_of_range

merge sort algorithm: std::out_of_range

c++

algorithm

mergesort