(* une autre vision du tri par fusion: Aho-Ullmann page 85 *)

(* egrem ou split *)
(* on définit simultanément : - une procédure de fendage d'une liste
										- une fonction de fusion de deux listes
elles s'entre-appellent pour tout trier 
*)

let rec egrem = function
	|[] -> ([],[])
	|[a] -> ([a],[])
	|(a::b::z) -> let (u,v)= egrem z in (a::u,b::v)
;;

let rec merge a b= match (a,b) with 
	|([],_) -> b
	|(_,[]) -> a
	|(ta::qa,tb::qb) -> if ta<=tb 
							  then (ta::(merge qa b))
							  else (tb::(merge a qb))
;;

let rec tri = function
	|[] -> []
	|[a] -> [a]
	|liste -> let (x,y)=egrem liste in merge (tri x) (tri y)
;;