Thread: 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

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.

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!