Merge sort algorithm?

[ItecKid]

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

[StuXYZ]

Hi,

Ok this is a post about HOWTO find your errors, which will result in actually finding one of your problems, but it is more a breakdown of what you should be doing.

(a) Ok write some output and it doesn't work.
(b) See that your input look ok for now. [It is random ish]
(c) What function is called first and what does it call.
-- Merge_sort
-- merge_sort and merge at the end.
(d) Is the input for merge ok.
-- put a return list at the top of merge().
(e) Check that left and right are correct AFTER one iteration.
-- put a return left; after the first loop in merge().
--- PROBLEM. This returns 1,2,3,4,5

Observe that you have written push_back(i) NOT push_back(list[i]) Further, note, that there is a std::list and since you insist on using using namespace std; I am 99% certain that latter that is going to bite you in the foot. [Not yet since you haven't included list but I am sure you will when you optimize it.]

Note that is not all of your problems but shows you how to go about debugging a problem.

Additionally, I would almost certainly start with setting the initial array to say 1,2,3,4,5,6,7,8 and then a random mix of those numbers.

Hope this helps. I would like to think that the rest of the bugs in your code are not just fixed by asking questions here, unless you show how you have started to debug.

[ItecKid]

Hello,

I have fixed my problem by changing code, as per your suggestion, to change

right.push_back(i)

to

right.push_back(list[i])

And the same thing for left.

Thank you very much for your help.

[zerothefoolwins]

If this is for wick's class, I would like to say this is able to be found on Google and might compromise the security of it. I'm not taking it, just to let you know some one else might have tried. If I sound crazy and not pertaining to you, sorry, I am mistaken.

[Calbert21]

OK, I am just about submitting a patent application for a new merge-sort algorithm that does optimal comparisons with O(N) data moves by taking advantage of the ability of the CPU to handle bit data. This can be coded in Java or C++ easily.

[Calbert21]

This algorithm is not for novice. In addition, from comparason to QuickSort it is not suitable for small data set. It performs best with large data sets and allow sorting to be done with variable length records quite easily. In addition, there are several implementation version of the main algorithm that allows a user to sort without moving a single record and to do search using the binary or linear algorithm.

There are practical advantage in the algorithm's implementation which is what is been patented! So we are now doing some test and a business plan along with a patent application. You probably would like to join us at some later stage?