-2

I wrote a mergesort function in c++. In which a pass wrong value(array out of bound) of upper limit in function.

int a[]={6,5,2,4,6,78,88,76,33,44,54,212,344,56,677};
int n=sizeof(a)/sizeof(a[0]);
printf("n=%d\n",n);
merges(a,0,n);   // if should be 'merges(a,0,n-1)'
printf("n=%d\n",n);

I think in argument only copy of a variable is passed. Original value does not change. but Checking before and after merges() function I got two different values. I can't figure out why? output:

n=15
n=677

Here is complete code:

#include<bits/stdc++.h>
using namespace std;
void mergeit(int a[],int l,int mid,int r)
{
    int n1=mid-l+1;
    int n2=r-mid;
    int ll[n1+1];ll[n1]=INT_MAX;
    for(int h=0;h<n1;h++)ll[h]=a[l+h];
    int rr[n2+1];rr[n2]=INT_MAX;
    for(int h=0;h<n2;h++)rr[h]=a[mid+1+h];
    int i=0,j=0;
    for(int k=l;k<=r;k++)
    {
        if(ll[i]<rr[j])
        {
            a[k]=ll[i];i++;
        }
        else{a[k]=rr[j];j++;}
    }
}
void merges(int a[],int l,int r)
{
    if(l<r)
    {
        int mid=(l+r)/2;
        merges(a,l,mid);
        merges(a,mid+1,r);
        mergeit(a,l,mid,r);
    }
}

int main()
{
    int a[]={6,5,2,4,6,78,88,76,33,44,54,212,344,56,677};
    int n=sizeof(a)/sizeof(a[0]);
    printf("n=%d\n",n);

    merges(a,0,n);   //array out of bound- it should be 'merges(a,0,n-1)'
    printf("n=%d\n",n);


}
Sahil S.
  • 59
  • 7

1 Answers1

0

It happens because when you write to memory out of bounds, the program's behaviour is undefined. One possible behaviour that may be observed is that n changes in value.

The language does not specify any guarantees about the behaviour of the program. But from the implementation perspective, it is quite possible, that n and a[n] happen to share the same address on the stack.

eerorika
  • 232,697
  • 12
  • 197
  • 326