(* Tri par insertion d'une liste d'entiers. *)

(* exercice 2.19 *)
let rec insert x = function
  | y :: l when y < x -> y :: insert x l
  | l -> x :: l

let rec insertion_sort = function
  | [] | [_] as l -> l
  | x :: l -> insert x (insertion_sort l)

(* notes

   - Il n'est pas nécessaire de faire un cas particulier pour la liste
     à un élément

   - On aurait pu écrire plus simplement encore

       List.fold_left (fun acc x -> insert x acc) [] l

   - Le chapitre 12 consacré aux tris contient une version plus
     élaborée pour éviter un débordement de pile.
*)

This document was generated using caml2html