0

I am trying to generate a random vector of integers and sort them using merge sort.
I am having trouble with the code. It is long, but I would appreciate if someone could take a look at it and see if the can help me, I've been working on it for days and am completely stuck.
When I run the program, it just stops at the point where I call the mergesort. I believe the problem may be in the merge split, because when I cout the values for low, high, and half there, I get 0 1 and 1, and this never changes. Thanks for the help.

#include <iostream>
#include <vector>
using namespace std;

vector<int> merge(vector<int> list1, vector<int> list2){
	vector<int> result;
	int int1=0;
	int int2=0;
	cout << "merging lists" << endl;
	while(int1 < list1.size() || int2 < list2.size())
	{
		if (int1 < list1.size() && int2< list2.size())
		{
			if (list1[int1] < list2[int2])
					result.push_back(list1[int1++]);
				else 
					result.push_back(list2[int2++]);
			}
			else{
				while(int1 < list1.size())
					result.push_back(list1[int1++]);
				while(int2 < list2.size())
					result.push_back(list2[int2++]);
			}
		}
		return result;
	}

vector <int> merge_split(vector<int> list, int low, int high){
	cout << "performing merge split" << endl;
	int half = ((high +1) - low)/2;
	cout << low << "  " << high << "  " << half << endl;
	if (high = low){
		vector<int> res;
		res.push_back(list[low]);
		return res;
	}
	else if (high - low == 1){
		vector <int> res;
		if(list[low] < list[high]){
			res.push_back(list[low]);
			res.push_back(list[high]);
		}
		else {
			res.push_back(list[high]);
			res.push_back(list[low]);
		}
	}
		vector<int> list1 = merge_split(list, low, low + half);
		vector<int> list2 = merge_split(list, low + half + 1, high);
		return merge(list1, list2);
}

void merge_sort(vector<int> &list){
	cout << "performing merge sort" << endl;
	int low = 0;
	int high = list.size() - 1;
	list = merge_split(list, low, high);
	return;
}

int main(){
	int i;
	vector <int> list;
	for (i = 0; i < 20; i++){
		list.push_back(rand());
	}
	int size = 20;
	cout << "Before" << endl;
	for (i = 0; i < size; i++)
		cout << list[i] << "  ";
	cout << endl;
	merge_sort(list);
	cout << "merge sort, after" << endl;
	cout << "After";
	for(i = 0; i < size; i++){
		cout << list[i] << "  ";
	}
	cout << endl;
	return 0;
}
2
Contributors
1
Reply
2
Views
10 Years
Discussion Span
Last Post by Ancient Dragon
0

You need to pass those vectors by reference instead of by value to avoid duplicating the vectors and so that the changes will be available to the calling function vector<int> merge(vector<int>& list1, vector<int>& list2){

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.