Hello,
I am attempting to write the merge sort algorithm which will generate a vector of 20 random integers and then sort them. The problem is, it does not output the sorted list, it merely outputs a series of zero's and one's. My code is as follows, any help is much appreciated.
#include <iostream>
#include <vector>
#include <cstdlib>
#include <time.h>
using namespace std;
//function parameter
vector <int> merge (const vector <int> &left, const vector <int> &right);
vector <int> merge_sort (const vector <int> &list);
//merge sort
vector <int> merge_sort (const vector <int> &list)
{
vector <int> left;
vector <int> right;
vector <int> result;
if (list.size() <= 1) { //returns the list if it is only 1 or less numbers
return list;
}
int middle = (list.size() / 2); //creates a pivot point
for (unsigned int i = 0; i < middle; i++) { //places all the numbers below the mid-point into a vector
left.push_back(i);
}
for (unsigned int i = middle; i < list.size(); i++) { //places all the numbers above the mid-point into a vector
right.push_back(i);
}
left = merge_sort(left);
right = merge_sort(right);
result = merge(left, right);
return result;
}
vector <int> merge (const vector <int> &left, const vector <int> &right)
{
vector <int> result;
const int left_size = left.size(), right_size = right.size();
int left_index = 0, right_index = 0;
while (left_index < left_size && right_index < right_size) {
if (left[left_index] < right[right_index]) {
result.push_back(left[left_index]);
left_index++;
}
else {
result.push_back(right[right_index]);
right_index++;
}
}
if (left_index == left_size) {
while (right_index < right_size) {
result.push_back(right[right_index]);
right_index++;
}
}
else {
while (left_index < left_size) {
result.push_back(left[left_index]);
left_index++;
}
}
return result;
}
int main (void)
{
//create a series of 20 random integers, then add them to the vector
vector <int> random_list;
for (int i = 0; i < 20; i++) {
random_list.push_back(rand());
}
for (int i = 0; i < random_list.size(); i++) {
cout << random_list.at(i) << endl;
}
vector <int> sort_list;
sort_list = merge_sort (random_list);
for (int i = 0; i < sort_list.size(); i++) {
cout << sort_list.at(i) << endl;
}
return 0;
}