Recursion misbehaving in merge sort

Question

The second recursion in my program is passing a weird array and then the entire process is getting ruined. I pass an array and its size which is then divided into two arrays left_arr and right_arr. We continue the above process for the left array until it hits the base condition. There is a similar question where the program is passing high, low values and making changes on the same array. I want to know why my code is giving abrupt output. Ignore the conquer function as I was unable to check that due to the error occurred before approaching it.

I tried debugging my code by printing both original, left and right array but unable to find the error.
Ok, My first doubt is that the program is creating a new array every time,i.e pass by value? And, How do I debug such issues?

#include<bits/stdc++.h>

using namespace std;


 int conquer(int left_arr[],int right_arr[], int arr[]){
    int i=0,j=0,k=0;
    int length_left = sizeof(left_arr)/sizeof(left_arr[0]);
    int length_right = sizeof(right_arr)/sizeof(right_arr[0]);

                                               //int l = length_left + 
 length_right;

  while(i<length_left && j<length_right)
  {
      if(left_arr[i]<=right_arr[j])
      {
          arr[k++] = left_arr[i++];
      }
      else
      {
          arr[k++] = right_arr[j++];
      }
  }
  while(i<length_left)
  {
      arr[k++] = left_arr[i++];
  }

  while(j<length_right)
  {
      arr[k++] = right_arr[j++];
  }


                                                  for(int i=0; i<l;i++)
                                                  cout<<arr[i]<<" ";
                                                    cout<<endl;
return 0;
}

int divide(int *arr,int n)
{

 if(n<2)
  return 0;




  int mid=n/2;
  int x = n-mid;

  cout<<"  n ="<<n<<"  mid ="<<mid<<endl;

  int left_arr[mid];
  int right_arr[n-mid];             //for debug
                                    cout<<"arr:";
                                    for(int m=0;m<n;m++)
                                        cout<<arr[m]<<"  ";
                                    cout<<endl;


  for(int i=0;i<mid;i++)
      left_arr[i]=arr[i];          //for debug
                                   cout<<"Larr:";
                                   for(int k=0;k<mid;k++)
                                    cout<<left_arr[k]<<" ";

                                    cout<<endl;



  for(int j=mid;j<n;j++)
      right_arr[j] = arr[j];
                                cout<<"Rarr:";      //for debug
                                for(int j=mid;j<n;j++)
                                    cout<<right_arr[j]<<" ";

                                    cout<<endl<<endl;


   divide(left_arr,mid);
   divide(right_arr,x);

   //conquer(left_arr,right_arr,arr);


  return 0;
}


int main()
{
  int n,arr[]={2,5,4,6,1,8,3};


  divide(arr,7);

  for(int i=0;i<7;i++)
  {
      cout<<arr[i]<<" ";
  }
    return 0;
}

n =7 mid =3 arr:2 5 4 6 1 8 3 Larr:2 5 4 Rarr:6 1 8 3

n =3 mid =1 arr:2 5 4 Larr:2 Rarr:5 4

n =2 mid =1 arr:7536080 5 Larr:7536080 Rarr:5 //error from here

n =4 mid =2 arr:-1 0 4200483 6 Larr:-1 0 Rarr:4200483 6

n =2 mid =1 arr:-1 0 Larr:-1 Rarr:0

n =2 mid =1 arr:7536080 5 Larr:7536080 Rarr:5

`int left_arr[mid];` is not standard C++ unless `mid` is a constant expression. This may or may not be part of the problem, but you should not be using the non-standard language extension. — crashmstr, Jul 10 '19 at 18:31
`int length_left = sizeof(left_arr)/sizeof(left_arr[0])` is a bug. At least is standard `c++`. `sizeof(left_arr)` is the size of a pointer not the size of an array. — drescherjm, Jul 10 '19 at 18:53
@OP You know that **all** of the bugs found so far could have been prevented if you used `std::vector` and its facilities, such as the `at()` call to determine boundary access issues. Even the `sizeof` bug mentioned is prevented by using `size()`. These are the reasons why the VLA syntax is bad for your health. It hides errors, and worse it causes errors if the number of entries is very high (stack overflow). — PaulMcKenzie, Jul 10 '19 at 18:55
`#include` [loads the gun](https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h). `using namespace std;` [takes the safety off](https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice). Be really careful. — user4581301, Jul 10 '19 at 19:09

score 1 · Answer 1 · answered Jul 10 '19 at 18:37

1

It's a simple array access out of bounds error (and therefore undefined behaviour).

for(int j=mid;j<n;j++)
    right_arr[j] = arr[j];

should be

for(int j=mid;j<n;j++)
    right_arr[j-mid] = arr[j];

Also, as already pointed out in the comments, you are using variable length arrays (VLAs) which are not legal C++.

answered Jul 10 '19 at 18:37

john

85,011
4
57
81

Please take a look at **conquer** function as well. I'm getting **1 0 2 0 1 8 3** as my final output after sorting. – Harshal Sharma Jul 10 '19 at 18:48
@HarshalSharma This code is incorrect `int length_left = sizeof(left_arr)/sizeof(left_arr[0]);` because `left_arr` is a pointer not an array. So `sizeof(left_arr)` is 4 (or 8 on a 64-bit system). It's not the size of the original array. Arrays are rubbish in C++, you should really be using vectors, but if you must use arrays then you should learn properly what they can and cannot do. – john Jul 10 '19 at 18:57

score 1 · Accepted Answer · answered Jul 10 '19 at 19:14

Do,

    for(int j=mid;j<n;j++)
    right_arr[j-mid] = arr[j];

And pass the size of whole array

   conquer(left_arr,right_arr,arr,n);

In conquer function,

    int length_left = n/2;
    int length_right = n-length_left;

as you cannot find the length of array from its pointer.

Recursion misbehaving in merge sort

2 Answers2