Tri par sélection en place

let tri_selection t =
  let n = Array.length t in
  for i = 0 to n - 2 do
    let imin = ref i in
    for j = i + 1 to n - 1 do
      if t.(j) < t.(!imin) then imin := j
    done;
    let tmp = t.(i) in
    t.(i) <- t.(!imin);
    t.(!imin) <- tmp
  done

Invariant (boucle externe) : au début de l'étape i, les cases 0..i-1 contiennent, triés, les i plus petits éléments du tableau. À la fin (i = n-1), tout est trié. Le tri est en place : aucune allocation, on échange des cases.