Random values when using merge in merge sort C++

Question

For a small homework assignment, I'm supposed to write a simple merge function whose prototype looks like this:

void merge(int a[], int left_low,  int left_high, int right_low, int right_high)

The directions say that for simplicity's sake, we are only taking in a single array, a[] and that right_low = left_high + 1. We are also storing the final values in the original array a[] that was passed in. Essentially, for an array with values a[] = {1,3,10,4,7,8} it looks like this:

a = {1, 3,     10 ,         4,    7,      8}
     ^         ^            ^             ^ 
  left_low  left_high    right_low     right_high

For this assignment, we have a few tests we have to pass. The first one is a simple merge between two arrays. The second is the teachers own merge_sort function that he calls on some randomly sorted arrays. Here is my implementation of merge():

void merge(int a[], int left_low,  int left_high,
                    int right_low, int right_high) {
    int temp[right_high + 1]; // temporary array to store the result
    int left_i = left_low, right_i = right_low, temp_i = 0;

    // while the temporary array is not filled
    while(temp_i != right_high + 1)
    {
        if(left_i == left_high + 1)
            temp[temp_i++] = a[right_i++];
        else if(right_i == right_high + 1)
            temp[temp_i++] = a[left_i++];
        else if(a[left_i] < a[right_i])
            temp[temp_i++] = a[left_i++];
        else
            temp[temp_i++] = a[right_i++];
    } // end while
    for(int i = 0; i < temp_i; ++i)
        a[i] = temp[i];
}

When he calls the first test, where he just checks the merging of two arrays, my function works, and the single array is now sorted. However, when he calls his merge_sort function, I end up getting garbage values. Here are his test functions:

template<class T>
void print (std::string label, T a[], int length, bool report_sorted) {
  bool sorted = true;
  std::cout << label;
  for (int i=0; i<length; ++i) {
    std::cout << a[i];
    if (i == length-1)
      std::cout << std::endl;
    else {
      std::cout << ", ";
      if (a[i] > a[i+1])
        sorted = false;
    }
  }
  if (report_sorted)
    std::cout << (sorted ? "    Sorted" : "    Not Sorted") << std::endl;
}

void shuffle(int values[], int length) {
  std::vector<int> v_values;
  for (int i=0; i<length; ++i)
    v_values.push_back(values[i]);
  std::random_shuffle(v_values.begin(),v_values.end());
  for (int i=0; i<length; ++i)
    values[i] = v_values[i];
}

//Recursive Merge Sort
template<class T>
void merge_sort(T a[], int low, int high) {
  if (high - low < 1)               //Base case: 0 or 1 value to sort -> sorted
    return;
  else {
    int mid = (low + high)/2;       //Split in 1/2
    merge_sort(a, low, mid);        //Recursively sort low to mid
    merge_sort(a, mid+1, high);     //Recursively sort mid+1 to high
    merge(a, low,mid, mid+1,high);  //Merge sorted parts of array
  }
}

//Standard Merge Sort (calls a generalized one, with more parameters)
template<class T>
void merge_sort(T a[], int length) {
  merge_sort(a, 0, length-1);
}

std::cout << "\n\nTesting merge in merge sort" << std::endl;
    int test_merge_sort[10] = {1,2,3,4,5,6,7,8,9,10};
    for (int i=0; i<5; i++) {
      shuffle(test_merge_sort, 10);
      print("\n  Array before sort: ", test_merge_sort, 10, false);
      merge_sort(test_merge_sort, 10);
      print("  Array after  sort: ", test_merge_sort, 10, true);
    }

And for some reason, my output ends up looking like this:

 Array before sort: 3, 9, 2, 5, 8, 4, 6, 10, 1, 7
  Array after  sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
    Not Sorted

  Array before sort: 1995111146, 1975317641, 4, 0, -944749486, 5443192, 5443196, 5439488, 4, -944749486
  Array after  sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
    Not Sorted

  Array before sort: -944749486, -944749486, 5443196, 4, 5439488, 1995111146, 5443192, 1975317641, 0, 4
  Array after  sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
    Not Sorted

  Array before sort: 1975317641, -944749486, 4, 4, 5439488, 5443192, 5443196, -944749486, 0, 1995111146
  Array after  sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
    Not Sorted

  Array before sort: -944749486, 5443192, 5443196, 1975317641, 4, 0, -944749486, 5439488, 1995111146, 4
  Array after  sort: -944749486, 4, 5439488, 0, 5443192, 5443196, 1975317641, -944749486, 4, 1995111146
    Not Sorted

What is going wrong with my merge code that could be causing this?

Answer 1

The problem is that you are computing the number of entries in temp incorrectly: your code thinks it is right_high + 1, but the correct formula is right_high - left_low + 1.

For example, when a call gives you indexes 10, 15, 16, 26, your code tries to merge 27 values, while it should be merging only 17 (i.e. indexes 10 through 26, inclusive).

This makes no difference when left_low is zero, so your test case runs fine. But as soon as left_low becomes nonzero, e.g. when the right half of the array is being sorted, your code "overshoots" both arrays, placing garbage values into tmp and writing over values in the array a as well.

Also the assignments in the last for loop need to be at offset left_low as well:

for(int i = 0; i < temp_i; ++i)
    a[i+left_low] = temp[i];