Recursive Merge Sort Algorithm Implementation

Question

I am a newbie to Algorithm. I try to implement recursive merge sorting using std::vector. But I am stuck. The code does not work.

I have looked at the algorithm from Introduction To Algorithms, Cormen/Leiserson/Rivest/Stein 3rd edition. The pseudocode which is I try to implement.

Here my merge function:

void merge(std::vector<int>& vec, size_t vec_init, size_t vec_mid, size_t vec_size) {
  int leftLoop = 0;
  int rightLoop = 0;
  int vecLoop = 0;
  size_t mid = vec_mid - vec_init + 1;

  std::vector<int> Left_Vec(std::begin(vec), std::begin(vec) + mid);
  std::vector<int> Right_Vec(std::begin(vec) + mid, std::end(vec));

  for (size_t vecLoop = vec_init; vecLoop<vec_size; ++vecLoop) {
      vec[vecLoop] = (Left_Vec[leftLoop] <= Right_Vec[rightLoop]) ? Left_Vec[leftLoop++] : Right_Vec[rightLoop++];
  }
}

And here my Merge-Sort function

void merge_sort(std::vector<int>& vec, size_t vec_init, size_t vec_size) {
    if (vec_init < vec_size) {
      size_t vec_mid = (vec_init + vec_size) / 2;
      merge_sort(vec, vec_init, vec_mid);
      merge_sort(vec, vec_mid + 1, vec_size);
      merge(vec, vec_init, vec_mid, vec_size);
   }
}

When the input vec = {30,40,20,10}, the output vec = {10, 10, 0, 20}:

int main() {
    auto data = std::vector{ 30, 40, 20, 10 };
    merge_sort(data, 0, data.size());
    for (auto e : data) std::cout << e << ", ";
    std::cout << '\n';
    // outputs 10, 10, 0, 20, 
}

Where is my mistake about the algorithm or code?

What happens if you remove the +1 in merge_sort(vec, vec_mid+1, vec_size); — Jeffrey, Aug 14 '19 at 14:49
Your `merge` function is horribly broken. You're accessing memory outside the bounds of the vectors you've allocated. I'd take a look online at some working merge functions. You're trying to be too clever in the loop. You'll need at least two separate loops for that function to work. — scohe001, Aug 14 '19 at 14:51
When initializing `Right_Vec`, you copy `vec` upto `std::end(vec)`, even when sorting a part of it. — YSC, Aug 14 '19 at 14:55
The conceptual error here is that the merge function should only work on the specific parts it is told to merge. Your variable names indicate that you think it is supposed to work on the whole vector, and the code does just that. — Kenny Ostrom, Aug 14 '19 at 15:14
[Please see the merge sort implementation here](https://stackoverflow.com/questions/24650626/how-to-implement-classic-sorting-algorithms-in-modern-c). — PaulMcKenzie, Aug 14 '19 at 15:28
It would be more efficient to do a one time allocation of a full size working vector, then merge between the two vectors depending on the level of recursion, similar to the example in the [wiki article](https://en.wikipedia.org/wiki/Merge_sort#Top-down_implementation), but with a more efficient merge. The initial copy to the temp vector can be avoided using a pair of mutually recursive functions (one the merges original back to original, one that merges original to temp, each calls the other). — rcgldr, Aug 15 '19 at 00:58

krisz · Accepted Answer · 2019-08-15T13:47:10.847

There are a couple of problems. These changes will fix the code:

void merge(std::vector<int>& vec, size_t vec_start, size_t vec_mid, size_t vec_end) {
  size_t leftLoop = 0;
  size_t rightLoop = 0;
  size_t vecLoop = 0;
  // Not needed, much simpler if mid is relative to vec.begin()
  //size_t mid = vec_mid - vec_init + 1;

  // You didn't take vec_init and vec_size into account when calculating the ranges.
  std::vector<int> Left_Vec(std::begin(vec) + vec_start, std::begin(vec) + vec_mid);
  std::vector<int> Right_Vec(std::begin(vec) + vec_mid, std::begin(vec) + vec_end);

  // Values are not uniformly distributed in the left and right vec. You have to check for
  // running out of elements in any of them.
  for (/*size_t*/ vecLoop = vec_start; leftLoop < Left_Vec.size() && rightLoop < Right_Vec.size(); ++vecLoop) {
    //   ^~~~~ shadowed outer vecLoop  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    vec[vecLoop] = Left_Vec[leftLoop] <= Right_Vec[rightLoop] ? Left_Vec[leftLoop++] : Right_Vec[rightLoop++];
  }

  // Copy the rest of the values into vec.
  if (leftLoop == Left_Vec.size())
    std::copy(Right_Vec.begin() + rightLoop, Right_Vec.end(), vec.begin() + vecLoop);
  else
    std::copy(Left_Vec.begin() + leftLoop, Left_Vec.end(), vec.begin() + vecLoop);
}

void merge_sort(std::vector<int>& vec, size_t vec_start, size_t vec_end) {
  // Should only run the function if there are at least 2 elements, otherwise vec_mid
  // would be always at least vec_start + 1 and the recursion would never stop.
  if (vec_end - vec_start >= 2) {
    size_t vec_mid = (vec_start + vec_end) / 2;
    merge_sort(vec, vec_start, vec_mid);
    merge_sort(vec, vec_mid /* + 1 */, vec_end);
    //                         ^~~ + 1 here would skip an element
    merge(vec, vec_start, vec_mid, vec_end);
  }
}

Recursive Merge Sort Algorithm Implementation

1 Answers1