mergeSort.cpp

#include "mergeSort.hpp"

/*
 *	takes two sorted vectors as parameters
 *	returns them merged together in a sorted way
 */
std::vector<int> MergeSort::merge(const std::vector<int> &input1, const std::vector<int> &input2) {

	std::vector<int> output;

	int index1 = 0, index2 = 0;

	while (index1 != input1.size() || index2 != input2.size()) {
		if (!(index1 < input1.size())) {
			output.insert(output.end(), input2.begin() + index2, input2.end());

			break;
		}

		if (!(index2 < input2.size())) {
			output.insert(output.end(), input1.begin() + index1, input1.end());

			break;
		}

		if ( input1[index1] < input2[index2]) {
			output.emplace_back(input1[index1]);

			index1++;
		} else {
			output.emplace_back(input2[index2]);

			index2++;
		}
	}

	return output;
}

/*
 *	takes a vector as input
 *	sorts the given vector using merge sort
 */
void MergeSort::mergeSort(std::vector<int> &input) {
	// don't do anything if the input vector has less than 2 elements
	if (input.size() < 2) {
		return;
	}
	// create new vector containing the first half of the input's elements
	std::vector<int> a(input.begin(), input.begin() + (input.size() + 1) / 2);
	// create new vector containing the second half of the input's elements
	std::vector<int> b(input.begin() + (input.size() + 1) / 2 , input.end());

	// merge sort each half
	mergeSort(a);
	mergeSort(b);

	// replace input vector with the sorted one merged together
	input = merge(a, b);
}