0

Here is the code. If any element in the array becomes greater than 16 then it just produces the wrong output. Looking for someone's help to point out my mistake.

#include<iostream>
using namespace std;

void merge(int A[], int p, int q, int r){
    int n1=q-p+1; // length of first subarray
    int n2=r-q; // length of second subarray
    int L[n1+1], R[n2+1]; // Size is taken n+1 to store sentinal at last
    int i,j,k;
    for(i=0;i<n1;i++){
        L[i]=A[p+i];
    }
    for(j=0;j<n2;j++){
        R[j]=A[q+j+1];
    }

    L[n1+1]=-1; // '-1' is a sentinal
    R[n2+1]=-1;
    i=0,j=0;
    for(k=p;k<r+1;k++){
        if(L[i]<=R[j]){
            A[k]=L[i];
            i=i+1;
        }
        else{
            A[k]=R[j];
            j=j+1;
        }
    }
}

void mergeSort(int arr[], int p, int r){
    int q;
    if(p<r){
        q=(p+r)/2;
        mergeSort(arr,p,q);
        mergeSort(arr,q+1,r);
        merge(arr,p,q,r);
    }
}

int main(){
    int n=8;
    int arr[n]={7,2,1,3,5,6,2,4}; // Not working for arr[i]>16
    mergeSort(arr,0,n-1);
    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
    }
return 0;
}

Please review my code and help me find the problem!

Anmol Upadhyay
  • 1
  • 2
    Your program uses [variable-length arrays](https://en.wikipedia.org/wiki/Variable-length_array), and those [are not part of C++](https://stackoverflow.com/questions/1887097/why-arent-variable-length-arrays-part-of-the-c-standard). Use `std::vector` instead. – Some programmer dude Dec 14 '21 at 06:39
  • 1
    I also recommend you take this opportunity to learn how to use a *debugger* to step through your code statement by statement, while monitoring variables and their values. I also recommend you use semantically relevant variable names rather than short one or two letter names, to make the code easier to read and understand. – Some programmer dude Dec 14 '21 at 06:41
  • Please provide the expected and actual output from your example code. (Demonstrating the functional failure might require changing your initial values since none of them are greater than 16.) – JaMiT Dec 14 '21 at 06:41
  • @Someprogrammerdude But I can't exactly get why I need to use vector for this program. It doesn't seem to be a vector problem. Also, if it is, can you brief me a little bit as why a variable length array. And yeah, thanks for your debugger suggestion, I'll surely start learning it. – Anmol Upadhyay Dec 14 '21 at 06:48
  • 1
    You use features that aren't standard C++. Variable-length arrays are typically taught on so-called "competition" or "online judge" sites, and such sites are *not* learning or teaching resources and should never be used as such! If you really want to learn programming and C++ properly, invest in [some good books](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list/388282#388282) and take classes. – Some programmer dude Dec 14 '21 at 06:50
  • 2
    Also don't forget the zero-based array indexes for arrays and vectors. If you have an array of `n1 + 1` elements, then the index `n1 + 1` will be *out of bounds* and lead to *undefined behavior*. – Some programmer dude Dec 14 '21 at 06:51

0 Answers0