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?).