(*permet d'inserrer un element dans une liste deja triee*)
let rec inserer = function
| (x, []) -> [x]
| (x, tete::[]) -> if x < tete then [x;tete] else [tete;x]
| (x, tete::queue) -> if x < tete then [x;tete] @ queue else [tete] @ inserer(x, queue);;
(* On peut alors definir le tri par insertion*)
let rec insertSort = function
| [] -> []
| tete::[] -> [tete]
| tete::queue -> inserer(tete, insertSort(queue));;