Tri par insertion. 

Profil : tri_insertion : int list -> int list
Sémantique : (tri_insertion l) = l' où l' contient tous les éléments de l et l' est triée par ordre croissant. 
             (tri_insertion [5;3;50:-6])=[-6;3;5;50]

Equations de récurrences: 

  tri_insertion [] = []
  tri_insertion x::l = (insertion x (tri_insertion l) )

avec insertion est implantée et déifinie.

   Profil : insertion: un entier, une liste d'entiers triée -> une liste d'entiers triée
   Sémantique : insertion e l : insère l'élément e dans la liste l tout en la gardant triée. 
                insertion 5 [-7;0;4;9;34] = [-7;0;4;5;9;34] 

   Equations de récurrences : 
      insertion e []   = [e]
      insertion e x::l = if (e<x) then e::x::l
                                  else x::(insertion e l)


=======================================================

Tri par pivot.

Equations de récurrences : 

  tri_pivot []   = []
  tri_pivot x::l = soit (pptpivot,pgdpivot)= (repartir_selon_valeur x l) 
                   dans (tri_pivot pptpivot)@[x]@(tri_pivot pgdpivot) 


fonction intermédiaire répartir_selon_valeur : 

   Profil : repartir_selon_valeur : un entier, une liste d'entiers -> une paire de listes d'entiers.
   Sémantique : (repartir_selon_valeur x l)=(l1,l2) avec l1 qui contient tous les éléments de l plus petit que x (inférieurs ou égaux), et l2 qui contient tous les éléments de l plus grand strictement que x. 
                (repartir_selon_valeur 12 [4;5;6;8;32;9;44])=([4;5;6;9],[32;44])
   Equations de récurrences : 
  repartir_selon_valeur x [] = ([],[])
  repartir selon_valeur x e::l = Soit (l1,l2)=(repartir_selon_valeur x l) dans 
                                     Si e>x alors (l1,e::l2)
				            sinon (e::l1,l2)

========================================================

Tri fusion
    tri_fusion [] = []
    tri_fusion x::l = soit (l1,l2)=coupe_en_deux l dans 
                      soit tl1=tri_fusion l1 dans 
                      soit tl2=tri_fusion l2 dans 
                           (fusion tl1 tl2)

    Fonctions intermédiaires 
    profil coupe_en_deux : une liste d'entiers -> un couple de liste d'entiers
    sémantique coup_en_deux l =(l1,l2) avec l1 et l2 qui ont tous les éléments de l, l1 en a la moitié et l2 l'autre moitié. 
    équations de récurrences : 
         coupe_deux [] = ([],[])
         coupe_deux x::l = soit (l1,l2)=(coupe_en_deux l) dans (x::l2,l1)


    fusion [] [] = []
    fusion x::l [] = x::l
    fusion [] x::l = x::l 
    fusion x1::l1 x2::l2 = if x1<x2 then x1::(fusion l1 x2::l2)
                                    else x2::(fusion x1::l1 l2)