[eyerandom]

Hi, I'm doing an assignment where I am supposed to implement a merge sort algorithm (shown below). Even though everything compiles, the elements are not actually sorted. I have been looking around for about an hour now and can't seem to figure out what is wrong with my code. Any input is greatly appreciated!

 void mergesort(vector<int> &data) {
  // implement me
	vector<int> left;
	vector<int> right;
	
	if (data.size() <= 1) {
		return;
	}
	else {
		int mid = (data.size()/2);
		
		
		for (int i = 0; i < mid; ++i) 
			left.push_back(data[i]);
		for (unsigned int i = mid; i < data.size(); i++) 
			right.push_back(data[i]);
	
		mergesort(left);
		mergesort(right);
		merge(left, right);

}
}

vector<int> merge(vector<int> &left, vector<int> &right) {
	vector<int> result;
	unsigned left_it = 0, right_it = 0;
	
	while (left_it <left.size() && right_it < right.size()) {
		if (left[left_it] < right[right_it]) { 
			result.push_back(left[left_it]);
			left_it++;
		}
		else {
			result.push_back(right[right_it]);
			right_it++;
		}
	}
	
	while(left_it < left.size()) {
		result.push_back(left[left_it]);
		left_it++;
	}
	
	while(right_it < right.size()) {
		result.push_back(right[right_it]);
		right_it++;
	}
	
	return result;
		
  // implement me

} 

[ButchDean]

Well, you haven't actually implemented the merge sort. Are you familiar with the actual algorithm?

[jimblumberg]

Here is a link that explains how the merge sort works. Merge Sort Algroithm.

Jim

[eyerandom]

ButchDean, on 07 February 2013 - 01:20 PM, said:

Well, you haven't actually implemented the merge sort. Are you familiar with the actual algorithm?

What do you mean by "implement?" I have a driver that implements it if that is what you mean. I think that there is a logic error that I am not seeing.

[ButchDean]

If it isn't doing what you expect then you haven't implemented it. Just by eyeballing your code I can see it doesn't look right.

[sepp2k]

Your merge_sort function is void and takes its argument by non-const reference. This suggests that it should modify the given vector in-place. But it never does that. It splits the vector into two halves and then it never does anything with the vector again. So the original vector remains unchanged. You should either modify the vector, or change the function to return a new sorted vector instead of being void. If you choose the latter, you need to change your recursive calls to use the return values.

Also you're never actually using the return value of your merge function. Just calling the function won't do anything, you need to use its return value. Since the function doesn't modify its argument, getting its return value is the only reason to call it.

On a style note the arguments to merge should be const references because, as I mentioned, it doesn't modify its argument.

[eyerandom]

derp. had to set data = merge(left, right). Thanks for the input!