Tri fusion

Exercice · OCaml (option informatique), chapitre 9 — Algorithmique : les tris

Énoncé

Écrire coupe et tri_fusion, et justifier le coût $Θ (n lo g n)$ .

Corrigé

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 $Θ (n)$ ; il y a $Θ (lo g n)$ niveaux car la taille est divisée par deux. Le coût est donc $Θ (n lo g n)$ , et ce dans tous les cas (contrairement au tri rapide).

Les autres exercices de ce chapitre Le cours du chapitre

Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.