Merge Sort Merge Procedure

Question

Guys i was trying to implement merge procedure of merge sort i found some interesting results.I don't know why it happened but if you know please comment and clear my doubt

This is my code

#include <iostream>

using namespace std;

void merge(void);

int main()
{
  merge();
   return 0;
}

void merge(){
     int p,q,r,i,j,k;
   int a[8]={1,5,7,8,2,4,6,9};
   
    cout<<"UnSorted list is";
    for(k=0;k<8;k++){
      cout<<a[k]<<"\t";
   }
   cout<<"\n";
   
   p=1;
   q=4;
   r=8;
   
   int n1,n2;
   n1=(q-p)+1;
   n2=r-q;
   
   int L[n1+1],R[n2+1];
   
   for(i=0;i<n1;i++){
       L[i]=a[p+i-1];
   }
   
   for(j=0;j<n2;j++){
       R[j]=a[q+j];
   }
   
   L[n1+1]=1000;//very large no.
   R[n2+1]=1000;
   
   
  i=0,j=0;
  
  for(k=0;k<8;k++){
      if(L[i]<=R[j]){
          a[k]=L[i];
          i++;
      }
      else{
          a[k]=R[j];
          j++;
      }
  }
  
  cout<<"Sorted list is \t";
   for(k=0;k<8;k++){
       cout<<a[k]<<"\t";
   }
   
   cout<<"\n";
}

Output

Well when i first time executed this program i got correct output but when i second time executed same program i got different output i don't know why.I am getting some garbage value don't know on second execution.When third time i executed i get correct Please help why its happening :)

Answer 1

from the code, 

   L[n1+1]=1000;//very large no.
   R[n2+1]=1000;

remove  $+1$

and rewrite as 

   L[n1]=1000;//very large no.
   R[n2]=1000;

Although these added numbers have no effect, the problem of garbage values is omitted since it was occurring because you were assigning value to an outside index (not to the last index) thus the last existing index was being filled w garbage.

 

TL; DR;

Last location in Array[10] = {} is not Array[10]; it’s Array[9].
Your L and R are of size n1+1, and n2+1 but you are assigning value 1000 to index [n1+1] and [n2+1] which doesn’t exist, the existing location is then filled w garbage.