#include <iostream>
#include <vector>

using namespace std;

void afficher(const vector<int> &vec)
{
	for(int i = 0; i < vec.size(); ++i)
		cout << vec[i] << " ";
	cout << endl;
}

vector<int> fusion(const vector<int> &vect1, const vector<int> &vect2)
{
	vector<int> ret;

	int k1 = 0;
	int k2 = 0;

	while(k1 < vect1.size() && k2 < vect2.size())
	{
		if(vect1[k1] < vect2[k2])
		{
			ret.push_back(vect1[k1]);
			k1++;
		} else {
			ret.push_back(vect2[k2]);
			k2++;
		}
	}
	
	for(; k1 < vect1.size(); ++k1)
		ret.push_back(vect1[k1]);
	
	for(; k2 < vect2.size(); ++k2)
		ret.push_back(vect2[k2]);

	return ret;
}

vector<int> tri_fusion(const vector<int> &vec)
{
	if(vec.size() <= 1)
		return vec;

	vector<int> vec1;
	vector<int> vec2;

	int i = 0;
	for(; i < vec.size()/2; ++i)
		vec1.push_back(vec[i]);
	for(; i < vec.size(); ++i)
		vec2.push_back(vec[i]);

	cout << "vec1 = ";
	afficher(vec1);

	cout << "vec2 = ";
	afficher(vec2);

	vector<int> vect1 = tri_fusion(vec1);
	vector<int> vect2 = tri_fusion(vec2);

	cout << "vect1 = ";
	afficher(vect1);

	cout << "vect2 = ";
	afficher(vect2);

	return fusion(vect1, vect2);
}

int main()
{
	vector<int> vec = {4,3,5,2,1,0};

	afficher(tri_fusion(vec));
}