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

// Fonction pour fusionner deux sous-tableaux
void fusionner(vector<int> &tableau, int gauche, int milieu, int droite)
{
	int n1 = milieu - gauche + 1;
	int n2 = droite - milieu;

	// Création de tableaux temporaires :
	vector<int> gaucheTab(n1), droiteTab(n2);

	// Copie des données dans les tableaux temporaires :
	for(int i = 0; i < n1; i++)
		gaucheTab[i] = tableau[gauche + i];
	for(int j = 0; j < n2; j++)
		droiteTab[j] = tableau[milieu + 1 + j];

	cout << "Fusion de [";
	for(int i = 0; i < n1; i++)
		cout << gaucheTab[i] << ',';
	cout << "\b] et [";
	for(int j = 0; j < n2; j++)
		cout << droiteTab[j] << ',';
	cout << "\b] : [";

	// Fusion des tableaux temporaires dans tableau[gauch ... droite]
	int i = 0, j = 0, k = gauche;
	while(i < n1 && j < n2)
	{
		if(gaucheTab[i] <= droiteTab[j])
		{
			tableau[k] = gaucheTab[i];
			i++;
		}
		else
		{
			tableau[k] = droiteTab[j];
			j++;
		}
		k++;
	}

	// Copie des éléments restants de gaucheTab (s'il y en a) :
	while(i < n1)
	{
		tableau[k] = gaucheTab[i];
		i++;
		k++;
	}

	// Copie des éléments restants de droiteTab (s'il y en a) :
	while(j < n2)
	{
		tableau[k] = droiteTab[j];
		j++;
		k++;
	}

	for(int x = gauche; x <= droite; x++)
		cout << tableau[x] << ',';
	cout << "\b]\n";
} // fusionner()

// Fonction de tri par fusion O(n log2(n))
void triParFusion(vector<int> &tableau, int gauche, int droite)
{
	if(gauche < droite)
	{
		// Calcul de l'indice du milieu :
		int milieu = gauche + (droite - gauche) / 2;

		// Appel récursif pour trier les deux moitiés :
		triParFusion(tableau, gauche, milieu);
		triParFusion(tableau, milieu + 1, droite);

		// Fusion des deux moitiés triées :
		fusionner(tableau, gauche, milieu, droite);
	}
} // triParFusion()

int main()
{
	vector<int> tableau = {38, 27, 43, 3, 9, 82, 10};

	cout << "Tableau initial : ";
	for(int val : tableau) cout << val << ' '; cout << '\n';

	triParFusion(tableau, 0, tableau.size() - 1);

	cout << "Tableau trié : ";
	for(int val : tableau) cout << val << ' '; cout << '\n';

	return 0;
} // main()