Le tri par tas du cours est-il en place ?

let tri_par_tas t =
  let f = tas_vide () in
  Array.iter (fun x -> inserer f x) t;
  Array.init (Array.length t) (fun _ -> extraire_min f)

Non, ce code n'est pas en place, et il faut le dire nettement : le chapitre décrit une méthode et en montre une autre.

Ce que ce code alloue. Un tas auxiliaire de $n$ éléments, puis un tableau résultat de $n$ éléments : $\Theta (n)$ de mémoire supplémentaire, et le tableau d'entrée t n'est pas modifié. C'est un tri hors place, exactement comme le tri par partition-fusion auquel le chapitre l'oppose. La version véritablement en place est celle du premier problème ci-après : on construit le tas dans le tableau lui-même, puis on échange la racine avec la dernière case, en $O(1)$ de mémoire supplémentaire.

L'hypothèse cachée. Array.init n f n'a de sens ici que si f est appelée sur $0,1,\dots ,n-1$ dans cet ordre : la fonction ignore son argument et lit un effet de bord, si bien qu'un ordre d'appel différent rendrait le tableau permuté, donc non trié. Mesuré sur la version installée (OCaml 5.4.1) : les appels ont bien lieu dans l'ordre croissant, et la documentation de Array.init le garantit — « tabulates the results of f applied in order to the integers 0 to n-1 ».

Mais c'est une garantie sur laquelle on ne devrait pas s'appuyer, parce que le lecteur ne peut pas la deviner : rien dans Array.init (Array.length t) (fun _ -> extraire_min f) ne dit que l'ordre compte. On préfère l'écriture qui le dit :

(* Renvoie un tableau trié contenant les mêmes éléments que t. t est inchangé.
   Complexité : Theta(n log n) en temps, Theta(n) en mémoire supplémentaire. *)
let tri_par_tas_hors_place t =
  let f = tas_vide () in
  Array.iter (fun x -> inserer f x) t;
  let n = Array.length t in
  if n = 0 then [||]
  else begin
    let r = Array.make n t.(0) in
    for i = 0 to n - 1 do
      r.(i) <- extraire_min f     (* l'ordre est ÉCRIT, pas supposé *)
    done;
    r
  end

Le principe : quand la correction d'un code dépend d'un ordre d'évaluation, on écrit une boucle. Une boucle for rend l'ordre visible ; un Array.init le cache. La différence ne se voit pas à l'exécution — jusqu'au jour où elle se voit.