0
    /*
This code is Written by Shankhadeep Dey
(15th Aug 2018)
*/
#include<iostream>
using namespace std;
void merge(int a[],int p,int q,int r)
{
    int n1,n2,j,i,k;
    n1= q-p+1;
    n2= r-q;
    int L[n1],R[n2];
    for (i = 0; i < n1-1; ++i)
        L[i]=a[p+i-1];
    for (j = 0; j < n2-1; ++j)
        R[j]=a[q+j];
    L[n1]=1e9;
    R[n2]=1e9;
    i=0;
    j=0;
    for (k = p; k < r; ++k)
    {
        if (L[i]<=R[j])
        {
            a[k]=L[i];
            i++;
        }
        else
        {
            a[k]=R[j];
            j++;
        }
    }
    while (i < n1)
    {
        a[k] = L[i];
        i++;
        k++;
    }

    /* Copy the remaining elements of R[], if there
       are any */
    while (j < n2)
    {
        a[k] = R[j];
        j++;
        k++;
    }
}
void mergeSort(int a[],int p,int r)
{
    int q;
    if (p<r)
    {
        q= (p+r)/2;
        mergeSort(a,p,q);
        mergeSort(a,q+1,r);
        merge(a,p,q,r);
    }
}
int main()
{   int w[4]={4,3,21,5};
    mergeSort(w,0,3);
    for (int i = 0; i < 4; ++i)
    {
        cout<<w[i]<<" ";
    }
    cout<<endl;
}

Can anyone tell me why this sorting is not working? I tried this algorithm from the book "Introduction to Algorithm" but I am not so sure why this code is not running. I tried searching online for merge sort and find so much things but I exactly want to know what is wrong with my code. Output is:-0 1000000000 1 1000000000 (which is not the correct ans).
This is the warning I'm getting

mergeSort.cpp: In function ‘void merge(int*, int, int, int)’:
mergeSort.cpp:12:10: warning: ISO C++ forbids variable length array ‘L’ [-Wvla]
  int L[n1],R[n2];
          ^
mergeSort.cpp:12:16: warning: ISO C++ forbids variable length array ‘R’ [-Wvla]
  int L[n1],R[n2];
Iamshankhadeep
  • 38
  • 1
  • 4
  • 2
    Define "not working". No output? Incorrect output? Crashes? Not compiling? – 9769953 Aug 15 '18 at 08:07
  • 2
    Have you tried turning on the compiler warnings, and read them? Those should reveal the problem. – 9769953 Aug 15 '18 at 08:10
  • 2
    From the outset, this is invalid C++. Turn up your compiler strictness (using `-pedantic` on clang/gcc). – Konrad Rudolph Aug 15 '18 at 09:22
  • Please [edit] your question to show us what kind of debugging you've done. I expect you to have run your [mcve] within Valgrind or a similar checker, and to have investigated with a debugger such as GDB, for example. Ensure you've enabled a full set of compiler warnings, too. What did the tools tell you, and what information are they missing? And read Eric Lippert's [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/). – Toby Speight Aug 15 '18 at 15:10
  • 1
    Stuff like `int L[n1],R[n2];` isn't valid C++, because [C++ doesn't have variable length arrays](https://stackoverflow.com/q/1887097/9254539). Code like this can sometimes compile because of a GCC non-standard extension. You should make your arrays fixed-sized or use `std::vector`. – eesiraed Aug 15 '18 at 17:49

1 Answers1

0

There are issues in your merge logic. Think about what happens when you want to merge the first two elements in the array. In this case, p=0, q=0 and r=1. In this case n1=0, and the following loop never executes:

for (i = 0; i < n1-1; ++i)
    L[i]=a[p+i-1];

Same with the next loop. Even worse, if you were to fix it by changing n1-1 to n1, then in the first iteration, p+i-1 would be -1, which would cause more problems.

If you want to cheat by comparing to a working solution, I believe that there is one at How to implement merge sort from "The Introduction to Algorithms" by Cormen and Co

More generally, I would suggest working with a line by line debugger (either gdb or by using an IDE like Eclipse) will allow you to step line by line through the code, checking what executes when and what variable values are at each step. This makes diagnosing errors like this much easier.

(Note: This problem was fixed in question edit).

There is a problem is in these lines:

for (int i = 0; i < n2-1; ++i)
    R[j]=a[q+j];

Either use j or i, but not both. At the moment you are using an uninitialised value of j.

On a side note, you declare the variables i and j twice (once near the top of the function, and again in the for loop). This doesn't stop the program from working, but having two variables with the same name at different scopes isn't great practice, as it could cause confusion.

Also, in this line:

q= (int)(p+r)/2;

the (int) part does nothing, and could mislead the reader. p and r are already integers, so the compiler uses integer division yielding an integer result.

Martin Cook
  • 554
  • 5
  • 15