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;
}