#include <stdio.h>
#include <stdlib.h>

void copierTableau(long* dest,long* src,size_t n){
	for(size_t i = 0;i < n;i++){
		dest[i] = src[i];
	}
}

void fusion(long* A,size_t p,size_t q,size_t r){
	size_t n1 = q-p;
	size_t n2 = r-q;
	long* Ag = malloc(n1*sizeof(long));
	long* Ad = malloc(n2*sizeof(long));
	copierTableau(Ag,A+p,n1);
	copierTableau(Ad,A+q,n2);
	size_t indG = 0;
	size_t indD = 0;
	size_t i = p;
	while(i < r){
		if(indG == n1){
			A[i] = Ad[indD];
			indD++;
		}else if(indD == n2){
			A[i] = Ag[indG];
			indG++;
		}else if(Ag[indG] < Ad[indD]){
			A[i] = Ag[indG];
			indG++;
		}else{
			A[i] = Ad[indD];
			indD++;
		}
		i++;
	}
	free(Ad);
	free(Ag);
}

void sousTriFusion(long* A,size_t p,size_t r){
	if(p+1 < r){
		size_t q = (p+r)/2;
		sousTriFusion(A,p,q);
		sousTriFusion(A,q,r);
		fusion(A,p,q,r);
	}
}

void triFusion(long* A,size_t n){
	sousTriFusion(A,0,n);
}

void printTab(long* A,size_t n){
	printf("{");
	for(size_t i = 0;i < n;i++){
		if(i != 0){
			printf(",");
		}
		printf("%ld",A[i]);
	}
	printf("}\n");
}

int main(int argc,char** argv){
	long* A = malloc((argc-1)*sizeof(long));
	for(size_t i = 0;i < argc-1;i++){
		A[i] = atol(argv[i+1]);
	}
	printf("Tableau d'entrée: ");
	printTab(A,argc-1);
	triFusion(A,argc-1);
	printf("Tableau de sortie: ");
	printTab(A,argc-1);
	free(A);
}