(**************************************************************************) (* *) (* Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre, *) (* Kim Nguyen, Laurent Sartre *) (* *) (* Informatique - MP2I/MPI - CPGE 1re et 2e années. *) (* Cours et exercices corrigés. Éditions Ellipses, 2022. *) (* *) (* https://www.informatique-mpi.fr/ *) (* *) (**************************************************************************) let rec insert x l = match l with | [] -> [x] | y :: _ when x <= y -> x :: l | y :: l' -> y :: insert x l' let rec insertion_sort = function | [] -> [] | x :: l -> insert x (insertion_sort l) let insertion_sort a = for i = 1 to Array.length a - 1 do let v = a.(i) and j = ref i in while 0 < !j && v < a.(!j - 1) do a.(!j) <- a.(!j - 1); decr j done; a.(!j) <- v done