(* 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 =fun
	|[]->([],[])
	|[a]->([a],[])
	|(a::b::z) -> let (u,v)= egrem z in (a::u,b::v)
;;

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

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