Algorithm: Can you Help me with my MergeSort implementation?

Hello there!

Glad to be a new member here!

I'm new to c++ coding, and I'm taking an algorithms course, and I've been having the hardest time implementing one of the basic Algorithms Merge-Sort, For those who recall how it works; My Merge-Step works fine

Code:

---

void merge(vector<int> array, int p, int q, int r) {
  int n1 = q - p + 1;
  int n2 = r - q;


  vector<int> left, right;
  vector<int>::iterator a_it = array.begin();


  for(int i = 0; i != n1; ++i)
    left.push_back(*(a_it + p + i -1));
  left.push_back(1000000); //sentinel


  for(int j = 0; j != n2; ++j)
    right.push_back(*(a_it + q + j));
  right.push_back(1000000); //sentinel

  array.clear();

  vector<int>::iterator i = left.begin(), j = right.begin();
 
  for(int k = 0; k < r; ++k) {   
    if(*i <= *j) {
      array.push_back(*i);
      ++i;
    } else {
      array.push_back(*j);
      ++j;
    }
  }
 
}

---

However my MergeSort recursive implementation does not work :(

Code:

---

void mergesort(vector<int> array, int p, int r) {
 if(p < r) {
    int q = floor((p + r) / 2);
    mergesort(array, p, q);
    mergesort(array, q + 1, r);
    merge(array, p, q, r - 1);
  }
}

---

The above code is based on the CLRS text book, So.. If I print the Array from within mergesort, it doesn't output the sorted array :(

Can you help me? Can you possibly spot where are the errors? I'm truly clueless..

Thanks in advance,

Best Regards,

J

The problem that immediately jumps out at me is that you are passing your vectors by value. This actually copies the whole vector and all of the items within it!
You will need to pass the vector by reference.

I haven't looked any further than that, because that completely and utterly prevents it from working in any way at all. Upon fixing that you will probably manage to make some progress on your own. Well see how it goes anyway.

Hi, thanks for the reply,

Actually, I had wondered if that was the problem myself. The only reason why I haven't made that change was because none of the similar examples I've seen in the web have reference params; However, I agree with you.. That has to be one of the main causes, If not the main cause for this malfunction. So, for argument's sake, where do you think I should pass a reference? in merge() or in mergesort();

Thank you for your reply once more :) very kind of you.

Quote:

---

Originally Posted by jlstr

where do you think I should pass a reference? in merge() or in mergesort();

---

yes.

also, p, q, and r are not very descriptive variable names, and it is impossible to determine what they do, without expending a significant amount of effort to understand your code.

Code:

---

void merge(vector<int> &array, int left, int middle, int right) { //zero based indexes
  int n1 = middle - left;
  int n2 = right - middle;


  vector<int> left_array, right_array; //two arrays are necessary; both are array/2
  vector<int>::iterator a_it = array.begin();


  for(int i = 0; i != n1; ++i)
    left_array.push_back(*(a_it + left + i));
  left_array.push_back(1000000); //sentinel


  for(int j = 0; j <= n2; ++j)
    right_array.push_back(*(a_it + right + j));
  right_array.push_back(1000000); //sentinel


  array.clear(); //NOT SURE IF I SHOULD DO THIS! But seems necessary or I'll just make a huge vector in each call


  vector<int>::iterator i = left_array.begin(), j = right_array.begin();
 
  for(int k = 0; k <= r; ++k) {   
    if(*i <= *j) {
      array.push_back(*i);
      ++i;
    } else {
      array.push_back(*j);
      ++j;
    }
  }


}

---

Code:

---

void mergesort(vector<int> &array, int left, int right) { //left and right and indexes


 if(left < right) {
    int middle = floor((left + right) / 2);
    mergesort(array, left, middle);
    mergesort(array, middle + 1, r);
    merge(array, left, middle, right);
  }


}

---

Hi there! I have updated the code :) Sorry for the less than descriptive arguments, it was only because it's like that in most text-books. :(

So, I asked this, but I think I mistyped.. Where should I use references? in merge()? OR in mergesort()? OR in both?

Anyway, The merge() seems to be working well, it's the recursive mergesort() that seems to mess up the left and right args passed.

Thanks again for the replies!

Is there anywhere where you actually want the entire vector to be copied, such that anything done to the copy has no effect on the vector that was passed in?
If not then there's nowhere where you want to pass it by value.

Also, you should get rid of those "sentinels" - find another way. They are a flawed way to stop yourself running off the end of the vector.