I am getting garbage values in my Merge Sort code

Question

I am trying to implement merge sort algorithm in C++. This is my code.Logic seems to be fine. But the output I'm getting is garbage values.I'm not able to get where the problem is in the code. I think my logic is correct but I'm not sure.

#include <iostream>
using namespace std;
void Merge(int A[],int L[],int nL,int R[],int nR);
void MergeSort(int A[]);

   //Function to Merge Arrays L and R into A. 
   //nL = number of elements in L
   //nR = number of elements in R. 
void Merge(int A[],int L[],int nL,int R[],int nR)
{ 
   // i - to mark the index of left subarray (L)
   // j - to mark the index of right sub-raay (R)
   // k - to mark the index of merged subarray (A)
   int i=0;
   int j=0;
   int k=0;
  while(i<nL && j<nR)
   {
      if(L[i]<=R[i])
      { A[k]=L[i];
        i=i+1;
      }
      else
      { A[k]=R[j];
        j=j+1;
      }
      k=k+1;
  }
  while(i<nL)
  { A[k]=L[i];
      i=i+1;
      k=k+1;
  }
  while(j<nR)
  { A[k]=R[j];
    j=j+1;
    k=k+1;
  }
}
// Recursive function to sort an array of integers. 
void MergeSort(int A[],int n)
{
  if (n<2) return;//base condition.If the array has less than two 
                     //elements, do nothing
  int mid=n/2;
   // create left and right subarrays
   // mid elements (from index 0 till mid-1) should be part of left sub- 
      //array 
   // and (n-mid) elements (from mid to n-1) will be part of right sub- 
      //array
  int left[mid];
  int right[n-mid];

  for(int i=0;i<mid-1;i++) left[i]=A[i];// create left subarray
  for(int i=mid;i<n-1;i++) right[i-mid]=A[i];// create right subarray

  MergeSort(left,mid);
  MergeSort(right,n-mid);
  Merge(A,left,mid,right,n-mid);
}

int main()
{ int A[]={2,4,7,1,5,3};
  int n=sizeof(A)/sizeof(A[0]);
  MergeSort(A,n);
  for(int i=0;i<n;i++) cout<<A[i]<<" ";

  return 0;
}

Expected output is 1 2 3 4 5 7

But actual is 0 -785903160 1 0(every time it's different)

Welcome to Stack Overflow! It sounds like you may need to learn how to use a debugger to step through your code. With a good debugger, you can execute your program line by line and see where it is deviating from what you expect. This is an essential tool if you are going to do any programming. Further reading: [How to debug small programs](http://ericlippert.com/2014/03/05/how-to-debug-small-programs/) and [Debugging Guide](http://idownvotedbecau.se/nodebugging/) — NathanOliver, Feb 13 '19 at 20:18
`int left[mid];` -- This is not valid C++. Arrays in C++ must have their sizes denoted by a constant expression, not a runtime value such as `mid`. Use `std::vector` instead. Once you start to use `vector`, you have access to using functions such as `at()` to check for boundary conditions. Don't be surprised if your errors are due to accessing elements out-of-bounds. — PaulMcKenzie, Feb 13 '19 at 20:21
dont use single letter variable names only (unless you want to participate in a 70s retro competition ;). This code is quite hard to read — 463035818_is_not_an_ai, Feb 13 '19 at 20:22
Also [read on how to implement sorting algorithms in C++](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). — PaulMcKenzie, Feb 13 '19 at 20:24
You should use std::vector rather than C-style arrays. The funcional header includes merge. — Michael Surette, Feb 13 '19 at 20:25

score 0 · Answer 1 · answered Feb 13 '19 at 22:13

This has been answered at, how-to-implement-classic-sorting-algorithms-in-modern-c. But I thought I'd post an answer that beginners my find valuable as I've seen this asked many times in the past. It must be a popular homework question.

In my opinion, if this is a modern C++ assignment, there should be a lot less of using indexing.

So in this implementation, I have not used std::merge and wrote the merge so some method could be seen.

Avoid the idiom: using namespace std; Why it is taught is beyond me. Typedef your types, it is much clearer.

using data_vect = std::vector<int>;

Hopefully this is clear enough and completely done with iterators. It is not as efficient as possible, the push_back in Merge could be avoided among other things. I DuckDucked this sort and the first few hits were not that great.

#include <iostream>
#include <vector>

using data_vect = std::vector<int>;
using dv_iter = data_vect::iterator;

data_vect Merge(data_vect& first, data_vect& second)
{
    data_vect result;
    dv_iter fval = first.begin();
    dv_iter sval = second.begin();
    for (;fval != first.end() || sval != second.end();)
    {
        if (fval == first.end())
            result.push_back(*sval++);
        else if (sval == second.end())
            result.push_back(*fval++);
        else if (*fval < *sval)
            result.push_back(*fval++);
        else
            result.push_back(*sval++);
    }
    return result;
}

void MergeSort(data_vect& input)
{
    int half = input.size() / 2;
    if (! half)
        return;

    data_vect left(input.begin(), input.begin() + half );
    data_vect right(input.begin() + half, input.end());

    MergeSort(left);
    MergeSort(right);
    input = Merge(left, right);
}

int main()
{
    data_vect A = { 6,2,7,4,1,5,3 };
    MergeSort(A);
    for ( auto& val : A )
        std::cout << val << " ";

    return 0;
}

Sebastiaan Alvarez Rodriguez · Answer 2 · 2019-02-13T22:17:20.210

Although understandable, it is not possibile in C++ to declare an array with a variable size, e.g. int[mSize]. All arrays must have a constant size, e.g. int[10] or

const int mSize = 10;
int[mSize] mArray...

You want a storage container which has a variable size. as @PaulMcKenzie suggested, you might want to use a Vector object. Your code would look something like this:

#include <iostream>
#include <vector>

using namespace std;
void Merge(vector<int>& A, vector<int>& L, vector<int>& R);
void MergeSort(vector<int>& A);

   //Function to Merge Arrays L and R into A. 
void Merge(vector<int>& A, vector<int>& L, vector<int>& R)
{ 
   // i - to mark the index of left subarray (L)
   // j - to mark the index of right sub-raay (R)
   // k - to mark the index of merged subarray (A)
   unsigned int i=0;
   unsigned int j=0;
   unsigned int k=0;
  while(i<L.size() && j<R.size())
   {
      if(L[i]<=R[i])
      { A[k]=L[i];
        i=i+1;
      }
      else
      { A[k]=R[j];
        j=j+1;
      }
      k=k+1;
  }
  while(i<L.size())
  { A[k]=L[i];
      i=i+1;
      k=k+1;
  }
  while(j<R.size())
  { A[k]=R[j];
    j=j+1;
    k=k+1;
  }
}
// Recursive function to sort an array of integers. 
void MergeSort(vector<int>& A)
{
  int n = A.size();
  if (n<2) return;//base condition.If the array has less than two 
                     //elements, do nothing
  int mid=n/2;
   // create left and right subarrays
   // mid elements (from index 0 till mid-1) should be part of left sub- 
      //array 
   // and (n-mid) elements (from mid to n-1) will be part of right sub- 
      //array
  vector<int> left(mid);
  vector<int> right(n-mid);

  for(int i=0;i<mid;i++) left[i]=A[i];// create left subarray
  for(int i=mid;i<n;i++) right[i-mid]=A[i];// create right subarray

  MergeSort(left);
  MergeSort(right);
  Merge(A,left,right);
}

int main()
{ vector<int> A={2,4,7,1,5,3};
  MergeSort(A);
  for(unsigned int i=0;i<A.size();i++) cout<<A[i]<<" ";

  return 0;
}

[Edit] I noticed I accidentally used comma's instead of dots in vector.size() calls. Also, I noticed 2 arrays stopping one item too early in copying left and right vectors.

Your code did not work. Above code compiles fine, but produces 1 3 5 2 4 7 as output. Also, have you thought of a vector of uneven length, such as 5 4 3 2 1?

At this point, the code will not split properly

Hi Sebastiaan, did you test your code before posting? I got a load of errors when I compiled. — lakeweb, Feb 13 '19 at 20:47
No I didn't. I wrote it on my phone, which does not have a compiler. I will boot my laptop and run this thing — Sebastiaan Alvarez Rodriguez, Feb 13 '19 at 22:00
You'll need to pass every `vector` by reference if you want to make lasting changes and avoid making copies. Also you probably want `A.size()` instead of `A,size()` in `main()`. — alter_igel, Feb 13 '19 at 22:13

I am getting garbage values in my Merge Sort code

2 Answers2