(* LE TRI PAR FUSION *)

let etale s=
	let long=string_length s in
	let tab=make_vect long "a" in
	for k=0 to long-1 do tab.(k)<-make_string 1 (nth_char s k) done;
	tab;;

let test=list_of_vect(etale "le tri par fusion");;

let rec affiche l=match l with
	|[]->()
	|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=do_list affiche ll; print_newline();; 

let rec affll2 ll=match ll with
	|[]->()
	|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  lt_string 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=map listemoica l ;;

	(* trifusion avec les listes de listes *)
(* l'ensemble des deux fonction trifusionll & boulot fonctionne,
mais il doit y avoir moyen de faire une seule fonction, et d'avoir 
une liste de motifs plus facile à comprendre *) 
(* quand j'ai voulu le transformer en fuse_ch, je n'ai pas reussi à le comprendre*)


let rec trifusionll liste=match liste with
       |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 begin affll2 ll;print_newline();boulot (trifusionll ll) end
;;

	(* la commande finale *)
let trifusion m = 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