Error in function returning pointers

[nitishkj]

#include<iostream>

using namespace std;

int* Merge(int* a,int* b,int m,int n) {

  int ans[m+n-1],i=0,j=0,k=0;

  while(i<m || j<n) {
    if(i>=m) {
      ans[k] = b[j];
      k++;j++;
    }
    else if(j>=n) {
      ans[k] = a[i];
      k++;i++;
    }
    else if(a[i] > b[j]) {
      ans[k] = b[j];
      k++;j++;
    }
    else {
      ans[k] = a[i];
      k++;i++;
    }
  }
  return ans;
}


int* MergeSort(int* a,int n) {

  if(n==1) {
    return a;
  }
  else {
    int b[n/2-1],c[n-n/2-1];
    int* d,e;
    for(int i=0;i<n/2;i++) {
      b[i] = a[i];
      c[i] = a[n/2+i];
      if(n%2 == 1)
	c[i] = a[n];
    }
    d = MergeSort(b,n/2);
    e = MergeSort(c,n-n/2);
    return Merge(d,e,n,n-n/2);
  }
}

int main() {

  int a[] = {9,8,7,6,5,4,3,2,1};
  int* b;
  b = MergeSort(a,9);

  for(int i=0;i<9;i++)
    cout<<b[i]<<endl;
}

/*
I am getting the following errors :
mergesort.cpp: In function ‘int* Merge(int*, int*, int, int)’:
mergesort.cpp:7: warning: address of local variable ‘ans’ returned
mergesort.cpp: In function ‘int* MergeSort(int*, int)’:
mergesort.cpp:46: error: invalid conversion from ‘int*’ to ‘int’
mergesort.cpp:47: error: invalid conversion from ‘int’ to ‘int*’
mergesort.cpp:47: error: initializing argument 2 of ‘int* Merge(int*, int*, int, int)’

please help !!!!!
*/

[webJose]

Without trying to proof your MergeSort algorithm, I must point out that the errors are clear:

1. The function Merge() has "return ans;". The variable "ans" is local (a local array). Since "ans" is local to the function Merge(), its memory will be released as soon as the function returns (by means of the return keyword). Therefore, you'll be returning a pointer to memory that you can no longer read. This is bound to crash.

2. Your variable "e" in MergeSort() is not of type int*, it is of type int. It is confusing, I know, but it is the truth. My advise? One line per variable ALWAYS.

int* d;
int* e;

Finally, your arrays b[] and c[] in MergeSort() are being created using a non-standard extension of C++. The standard does NOT allow the creation of dynamic arrays in the stack. This is code that won't compile in any C++ compiler, except maybe just one (the one you are using, I guess). You should be allocating arrays in the heap using operator new().

[nitishkj]

Thanks for the answer, point no. 2 worked

as for 1, what do u advise me to do, given that i want to return the merged array ?

as for b[] and c[], correct me if i am wrong, but in line no. 37, i have intialized it to : int b[n/2-1],c[n-n/2-1];
n is fixed for a particular call, how are these arrays dynamic ?

i just modified the code according to point 2, and now its just giving a warning :

mergesort.cpp: In function ‘int* Merge(int*, int*, int, int)’:
mergesort.cpp:7: warning: address of local variable ‘ans’ returned

>This is code that won't compile in any C++ compiler, except maybe just one (the one you are using, I guess).
i am using the gcc compiler on linux terminal and except this warning its not giving anything else though its not giving me the correct answer on running, its returning garbage values.

[nitishkj]

I have changed my code to the following :

#include<iostream>

using namespace std;

int* Merge(int* ans,int* a,int* b,int m,int n) {

  int i=0,j=0,k=0;

  while(i<m || j<n) {
    if(i>=m) {
      ans[k] = b[j];
      k++;j++;
    }
    else if(j>=n) {
      ans[k] = a[i];
      k++;i++;
    }
    else if(a[i] > b[j]) {
      ans[k] = b[j];
      k++;j++;
    }
    else {
      ans[k] = a[i];
      k++;i++;
    }
  }
  return ans;
}


int* MergeSort(int* a,int n) {

  if(n==1) {
    return a;
  }
  else {
    int b[n/2-1],c[n-n/2-1];
    int* d;
    int* e;
    int* ans;

    for(int i=0;i<n/2;i++) {
      b[i] = a[i];
      c[i] = a[n/2+i];
      if(n%2 == 1)
	c[i] = a[n];
    }
    d = MergeSort(b,n/2);
    e = MergeSort(c,n-n/2);
    return Merge(ans,d,e,n,n-n/2);
  }
}

int main() {

  int a[] = {9,8,7,6,5,4,3,2,1};
  int* b;
  b = MergeSort(a,9);

  for(int i=0;i<9;i++)
    cout<<b[i]<<endl;
}

there are no warnings but i am getting segmentation fault on running....

[webJose]

And it comes with no surprise. Like I stated before, you are returning a memory pointer to memory that is being released. Released memory is usually overwritten with something else, and those are the garbage values you see.

About the array allocation: It is a dynamic array if the number or expression inside the brackets [] is NOT KNOWN at compilation time. The compiler is not smart enough to see that you are only trying to sort one array, and that the array to be sorted has been fixed at compilation time. To the compiler (a standard C++ compiler anyway), your use of variable n inside the brackets is as dynamic as it can be.

So, I don't know where you learned to allocate arrays in that way, but the smartest thing you can do for yourself is just forget about it. Use arrays allocated in the heap using operator new().

Check out the tutorial in this website, the section of arrays and dynamic memory.