Merge sort with Vectors

[d1g1talarts]

I am trying to implement a merge sort and the end result that i am getting is not quite sorted correctly. Anyone able to explain to me why?

 vector<int> merge(vector<int> left, vector<int> right) {
	int leftCount = 0;
	int rightCount = 0;

	vector<int> results;

	bool useLeft;
	for (int i = 0; i<left.size() + right.size(); i++) {
		if (leftCount<left.size()) {
			if (rightCount<right.size()) {
				useLeft = (left[leftCount] < right[rightCount]);
			}
			else {
				useLeft = true;
			}
		}
		else {
			useLeft = false;
		}

		if (useLeft) {
			results.push_back(left[leftCount]);
			if (leftCount < left.size()) {
				leftCount++;
			}
		}
		else {
			results.push_back(right[rightCount]);
			if (rightCount<right.size()) {
				rightCount++;
			}
		}
	}
	return results;
}

// merge sort function
vector<int> mergeSort(vector<int> arr) {
	if (arr.size() <= 1) {
		return arr;
	}
	int len = floor(arr.size() / 2);
	vector<int> left(arr.begin(), arr.begin() + len);
	vector<int> right(arr.begin() + len, arr.end());

	return merge(mergeSort(left), mergeSort(right));
}//emd of merge sort 

[helios]

I don't see anything wrong (algorithmically) with that code. Do you have a sample input that produces wrong output?

[keskiverto]

Your merge() has a lot of lines. The algorithm shown in http://www.cplusplus.com/reference/algorithm/merge/ has less. How does it differ from yours?

[tpb]

What do you mean "not quite sorted correctly".
Post a main with a test case that sorts incorrectly.

And your merge is overly complicated:

vector<int> merge(vector<int> left, vector<int> right) {
	size_t ileft = 0, iright = 0;
	vector<int> results;
	while (ileft < left.size() && iright < right.size()) {
	    if (left[ileft] < right[iright])
	        results.push_back(left[ileft++]);
	    else
	        results.push_back(right[iright++]);
	while (ileft  < left.size() ) results.push_back(left [ileft++ ];
	while (iright < right.size()) results.push_back(right[iright++];
	return results;
}

[d1g1talarts]

This is how i am testing merge sort

vector<int> checkVal = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
	vector<int> inputTest = { 15,12,13,11,9,10,7,8,14,6,5,3,4,2,1 };
	vector<int> inputTest2 = inputTest;
vector <int> tempTest=mergeSort(inputTest2);
	if (tempTest == checkVal) {
		sorted = true;
		cout << "Merge sort is funtional: " << sorted<<"\n";
	}
	else {
		cout << "Merge sort is not funtional: " << sorted<<"\n";
	}

and in the main

sorted = false;
	//Testing mergeSort
	vector <int> tempTest=mergeSort(inputTest2);
	if (tempTest == checkVal) {
		sorted = true;
		cout << "Merge sort is funtional: " << sorted<<"\n";
	}
	else {
		cout << "Merge sort is not funtional: " << sorted<<"\n";
	}
	//end of testing of binsearch quicksort and  

output spits out 1 7 12 15 13 9 11 10 5 8 14 6 3 4 2

[tpb]

Works for me:

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

vector<int> merge(vector<int> left, vector<int> right) {
	size_t ileft = 0, iright = 0;
	vector<int> results;
	while (ileft < left.size() && iright < right.size())
	    if (left[ileft] < right[iright])
	        results.push_back(left[ileft++]);
	    else
	        results.push_back(right[iright++]);
	while (ileft  < left.size() ) results.push_back(left [ileft++ ]);
	while (iright < right.size()) results.push_back(right[iright++]);
	return results;
}

vector<int> mergeSort(vector<int>& arr) {
	if (arr.size() <= 1)
		return arr;
	int len = arr.size() / 2;
	vector<int> left (arr.begin(),       arr.begin() + len);
	vector<int> right(arr.begin() + len, arr.end()        );
	return merge(mergeSort(left), mergeSort(right));
}

int main() {
    vector<int> checkVal = { 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15 };
    vector<int> inputTest = { 15,12,13,11,9,10,7,8,14,6,5,3,4,2,1 };
    vector <int> tempTest = mergeSort(inputTest);
    if (tempTest == checkVal)
        cout << "Sorted\n";
    else
        cout << "Not sorted\n";
    for (int n: tempTest) cout << n << ' '; cout << '\n';
}

[d1g1talarts]

Odd. Well if it works it works.

[helios]

OP's code sorts correctly without any modifications: http://cpp.sh/8sp5o (I just removed the call to floor() because it was redundant and I didn't want to include <cmath>).

[keskiverto]

output spits out 1 7 12 15 13 9 11 10 5 8 14 6 3 4 2

You did not show the code that spits those, did you?

If the sorting is correct and you see nonsense output, then you have error somewhere else.