Stack Smashing detected while implementing mergeSort in C++14

Question

I am implementing standart MergeSort algorithm. I am getting a runtime error 'Stack Smashing Detected'. What is the root cause of such error and how to prevent my code from this error? I saw that the control is coming to merge function , but somewhere it is getting messed up.


#include<iostream>
using namespace std;
//this particular function will merge 2 sorted array
void merge(int arr[], int res[], int low, int mid, int high) {
    
    int i=low,j=mid+1,k=high;
    while(i<=mid && j<=high) //make sure that i remains within the end if left subarray and j remains within the end of right subarray
    {
        if(arr[i]<=arr[j])
            res[k++]=arr[i++];
        else
            res[k++]=arr[j++];
    }
    while(i<=mid) // In case there are some elements left in left subarray, just copy it into result
       res[k++]=arr[i++];
       
    while(j<=high) //// In case there are some elements left in right subarray, just copy it into result
        res[k++]=arr[j++];
    //copy the result into original array 
    for( i=low;i<=high;i++)
        arr[i]=res[i];
    
 
}
void mergeSort(int arr[], int res[], int low, int high) {
    //Don't forget to put the base case in recursion
    if(high == low)
        return;
    int mid = low + (high-low)/2;
    mergeSort(arr,res,low,mid);
    mergeSort(arr,res,mid+1,high);
    merge(arr,res,low,mid,high);
    cout<<"end of recursion"<<endl;
 
}
int main() {
    int arr[] = {8,4,3,12,25,6,13,10};
    // initialise resultant array (temporary)
    int res[]= {8,4,3,12,25,6,13,10};
    
    for(int i=0 ;i<8 ; i++)
        cout<<arr[i]<<" ";
        cout<<endl;
    mergeSort(arr,res,0,7);
    for(int i=0 ;i<8 ; i++)
        cout<<arr[i]<<" ";
    cout<<endl;
    
}

The usual cause of stack smashing is code that writes to an area of the stack it shouldn't. In your case I would guess an out of bounds access to `arr` or `res`. — john, Sep 06 '22 at 14:59
In particular this line worries me `int i=low,j=mid+1,k=high;`, shouldn't that be `int i=low,j=mid+1,k=low;`? — john, Sep 06 '22 at 15:03
Yes, John. You are correct. If k==high then I guess res[k++]=arr[i++] is causing buffer overflow. — Subhadip, Sep 06 '22 at 15:05
[What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/questions/25385173/what-is-a-debugger-and-how-can-it-help-me-diagnose-problems) — Jesper Juhl, Sep 06 '22 at 15:08

score 2 · Accepted Answer · answered Sep 06 '22 at 15:22

The problem is in your merge routine. If you look at the case where low and mid are 6 and high is 7, which will happen towards the end of the recursion, the loop

while (i <= mid)
   res[k++] = arr[i++];

will end up executing with k being out-of-bounds. I think you meant for k to be initialized to low because it is supposed to be in sync with i.

Stack Smashing detected while implementing mergeSort in C++14

1 Answers1