Point d'insertion

let insertion x t =
  let g = ref 0 and d = ref (Array.length t) in   (* d exclusif *)
  while !g < !d do
    let m = (!g + !d) / 2 in
    if t.(m) < x then g := m + 1 else d := m
  done;
  !g

On cherche par dichotomie la frontière entre les < x et les >= x. g converge vers le nombre d'éléments strictement inférieurs à x : c'est exactement la position d'insertion. (Borne d prise exclusive ici, d'où Array.length t.)