let rec insereprof x l = match l with
| [] -> [x]
| t::q when t<x -> t::(insereprof x q)
| _-> x::l;;

let rec tri_insertion l = match l with
| [] -> []
| t::q -> insereprof t (tri_insertion q);;

let echange t i j =
  let x = t.(i) in
    t.(i) <- t.(j);
    t.(j)<- x
;;

let minimum t i =
  let m = ref i in
    for k = i+1 to Array.length t -1 do
      if t.(k)<t.(!m) then m:=k
      done;
      !m
;;

let tri_selection t =
  for i=0 to Array.length t -2 do
    echange t i (minimum t i)
  done;
  t
;;

let une_etape t i =
  let n = Array.length t and b = ref false in
    for k = n-1 downto i+1 do
      if t.(k-1)>t.(k) then
        begin
          echange t (k-1) k;
          b:=true
        end
      done;
  !b
;;

let tri_bulles t =
  let i = ref 0 in
    while une_etape t !i do
      i:=!i+1
    done;
    t
;;

let rec partition l = match l with
| [] -> [],[]
| [x] -> [x],[]
|t1::t2::q -> let q1,q2 = partition q in t1::q1,t2::q2
;;

let rec fusion l1 l2 = match l1,l2 with
| [],[] -> []
| [],l2 -> l2
| l1, [] -> l1
| t1::q1,t2::q2 -> if t1<t2 then t1::fusion q1 l2
                   else t2::fusion l1 q2
;;

let rec tri_fusion l = match l with
| [] -> []
| [x] -> [x]
| _ -> let l1,l2 = partition l in
  fusion (tri_fusion l1) (tri_fusion l2)
;;

let partition2 t d f =
  let i = ref d in
    for j = d+1 to f do
      if t.(j)<=t.(d) then
        begin
          i := !i+1;
          echange t !i j;
        end
      done;
      echange t d !i;
      !i;
;;

let rec tri_rapide_aux t d f=
  if f>d then
    begin
      let p = partition2 t d f in
        tri_rapide_aux t d (p-1);
        tri_rapide_aux t (p+1) f
    end
;;

let tri_rapide t = tri_rapide_aux t 0 (Array.length t-1);;