let rec trier inferieur l = match l with [] | [_] -> l | _ -> let l1,l2 = separer l in fusionner inferieur (trier inferieur l1) (trier inferieur l2);;
On sépare la liste en deux sous-listes, que l'on trie par un appel récursif, et on fusionne ensuite les deux listes triées. On rappelle qu'un tel algorithme met O(n log n) opérations, et qu'il n'existe pas d'algorithmes de tri par comparaison asymptotiquement plus rapides (à une constante près).
Remarquez que l'on traite, là encore, deux cas de base:
pour les listes de longueur nulle ou de longueur un (et qui sont donc
identiques à leur version triée). Il est nécessaire de traiter
les cas de longueur un. En effet, la fonction separer
ne produit de listes de taille strictement
inférieure à la taille n de son entrée que si
n>1. Si l'on ne prend pas en compte les cas de longueur un,
le programme part en récursion infinie (trier
se rappelle toujours sur le même argument)
et meurt par un Stack_overflow
:
$ ocaml Objective Caml version 3.07 # let rec separer = function [] -> [], [] | [x] -> [x], [] | x1::x2::tail -> let t1,t2 = separer tail in (x1::t1), (x2::t2);; val separer : 'a list -> 'a list * 'a list = <fun> # let rec fusionner inferieur l1 l2 = match l1,l2 with (l, []) | ([], l) -> l | (h1::t1), (h2::t2) -> if inferieur h1 h2 then h1::(fusionner inferieur t1 l2) else h2::(fusionner inferieur l1 t2);; val fusionner : ('a -> 'a -> bool) -> 'a list -> 'a list -> 'a list = <fun> # let rec trier inferieur l = match l with [] -> l | _ -> let l1,l2 = separer l in fusionner inferieur (trier inferieur l1) (trier inferieur l2);; val trier : ('a -> 'a -> bool) -> 'a list -> 'a list = <fun> # trier ( <= ) [1; 2];; Stack overflow during evaluation (looping recursion?).