Code source du tri "fusion"
let rec division liste=
match liste with
|[]->[],[]
|a::[]->liste,[]
|a::b::c->
let (l1,l2)=division c in
a::l1,b::l2;;
(* division : 'a list -> 'a list * 'a list = <fun> *)
let rec fusion liste1 liste2=
match liste1,liste2 with
|[],_->liste2;
|_,[]->liste1;
|t1::q1,t2::q2->
if t1<t2 then
t1::(fusion q1 liste2)
else
t2::(fusion liste1 q2);;
(* fusion : 'a list -> 'a list -> 'a list = <fun> *)
let rec tri_fusion liste=
match liste with
|[]->[];
|a::[]->liste;
|_ ->
begin
let (liste1,liste2)=division liste in
fusion (tri_fusion(liste1)) (tri_fusion(liste2));
end;;
(* tri_fusion : 'a list -> 'a list = <fun> *)