Tri fusion

let rec coupe l =
  match l with
  | [] -> ([], [])
  | [x] -> ([x], [])
  | x :: y :: reste ->
      let (a, b) = coupe reste in
      (x :: a, y :: b)

let rec tri_fusion l =
  match l with
  | [] | [_] -> l
  | _ ->
      let (a, b) = coupe l in
      fusion (tri_fusion a) (tri_fusion b)

À chaque niveau de récursion, le travail total (couper + fusionner) est $\Theta (n)$ ; il y a $\Theta (\log n)$ niveaux car la taille est divisée par deux. Le coût est donc $\Theta (n\log n)$, et ce dans tous les cas (contrairement au tri rapide).