(* LE TRI PAR FUSION *)

let etale s=
	let long=String.length s in
	let tab=Array.make long "a" in
	for k=0 to long-1 do tab.(k)<-String.make 1 s.[k] done;
	tab;;

let test=Array.to_list(etale "le tri par fusion");;

let rec affiche = function
	|[]->()
	|t::q->print_string" ";print_string t; affiche q
;;

(*le affiche ll qui suit affiche à l'envers! il est vrai que la nature d'une liste d'effets de bord n'est pas claire mais c'est quand même rigolo*)
let affichell ll=List.iter affiche ll; print_newline();; 

let rec affll2 = function
	|[]->()
	|t::q->affiche t; affll2 q
;;

	(* ci dessous la fusion de deux files *)
let rec fusion (a,b) =
    match (a,b) with
    ([],_) -> b
    | (_,[]) -> a
    | (t1::r1,t2::r2)-> if t1 < t2
                        then t1::fusion (r1,b)
                        else t2::fusion (a,r2)
   ;;

	(* transforme une liste en liste de listes *)
let listemoica t = [t];;
let listeliste l=List.map listemoica l ;;

	(* trifusion avec les listes de listes *)
let rec trifusionll = function
	|a::b::c -> begin
					(*	affll2 liste; print_newline(); *)
					fusion (a,b) :: trifusionll c
	     			end
	|a::_   -> [a]
	|_      -> []
;;

let rec boulot = function
   |[]->[]
   |t::r as ll-> if r=[]
                 then [t]
                 else (affll2 ll;print_newline();boulot (trifusionll ll))
;;

	(* la commande finale *)
let trifusion m = List.hd (boulot (listeliste m));;

(* la sortie de la fenêtre caml 
ce n'est pas vraiment comme les résultats analogues, les fusions ont lieu 
un peu partout en même temps, je n'ai pas réussi à obtenir un affichage par 
échange
 l e   t r i   p a r   f u s i o n
 e l   t i r   p a r   f s u i o n
   e l t   i p r   a f r i o s u n
     e i l p r t   a f i o r s u n
       a e f i i l o p r r s t u n
*)