c++recursionstackmergesortstack-smash

Stack Smashing detected while implementing mergeSort in C++14


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


Solution

  • 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.