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