Home > Back-end >  Stack Smashing detected while implementing mergeSort in C 14
Stack Smashing detected while implementing mergeSort in C 14

Time:09-07

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

CodePudding user response:

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.

  • Related