#include "Sorting.h"

vector<int> Sorting::mergesort(vector<int> input)
{
	int n = input.size();
	vector<int> low;
	vector<int> high;
	vector<int> result;
	if (n > 1)
	{
		vector<int> low = mergesort(vector<int>(input.begin(), input.begin() + n / 2));
		vector<int> high = mergesort(vector<int>(input.begin() + n / 2, input.end()));

		while (low.size()!=0&&high.size()!=0)
		{
			if (low.front() > high.front())
			{
				result.push_back(high.front());
				high.erase(high.begin());

			}
			else
			{
				result.push_back(low.front());
				low.erase(low.begin());
			}
		}
		if (low.size() == 0)
		{
			result.insert(
				result.end(),
				std::make_move_iterator(high.begin()),
				std::make_move_iterator(high.end())
			);

		}
		else
		{
			result.insert(
				result.end(),
				std::make_move_iterator(low.begin()),
				std::make_move_iterator(low.end())
			);

		}
	}
	else
	{

		result.push_back(input[0]);
	}return result;





}