merge sort algorithm: std::out_of

I am currently making a merge sort algorithm but when i run the code i get an error says "terminate called after throwing an instance of 'std::out_of_range". This is my code.

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];
    }
}

Merge Sort Function

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
    }
}

CodePudding user response：

A few issues in your merge function (which you can spot easily through debugging):

vec.at(i) <= m compares a value with an index. These two are unrelated. So change:
```
while(vec.at(i) <= m && j <= r){ 
```
with:
```
while(i <= m && j <= r){ 
```
The final loop starts with p = 1 which is an index that in many cases is out of the range that is being merged. So change:
```
for(size_t p = 1; p <= r; p  ){
```
with:
```
for(size_t p = l; p <= r; p  ){
```
The body of that same loop uses k as index, but that variable is unrelated to the loop, and has a value that is out of the range that is under consideration. So change:
```
vec.at(p) = temp[k];
```
with:
```
vec.at(p) = temp[p];
```

With those changes your code will work.

However, it is a pity that temp always has the size of the complete vector, while you only use a subsection of it. Consider reducing the memory usage.