let steps = [|1750; 701; 301; 132; 57; 23; 10; 4; 1|];; Random.self_init ();; let nswaps = ref 0;; let swap a i j = incr nswaps; let t = a.(i) in a.(i) <- a.(j); a.(j) <- t;; let insertion a d off = for i = 1 to (Array.length a - off) / d - 1 do let j = ref (i * d + off) in while (!j - d >= 0) && (a.(!j - d) > (a.(!j))) do swap a (!j - d) (!j); j := !j - d; done; done;; let shell a = let len = Array.length a in let stptr = ref 0 in while (steps.(!stptr) > len) do incr stptr done; while (!stptr < Array.length steps) do for off = 0 to steps.(!stptr) - 1 do try insertion a (steps.(!stptr)) off with Invalid_argument s -> failwith "insertion" done; incr stptr; done;; let print x = Array.iter (Printf.printf "%s ") x; print_newline ();; let rec random_string n = if n = 0 then "" else String.make 1 (char_of_int (Random.int 26 + 97)) ^ random_string (n - 1);; let test = Array.init 64 (fun _ -> random_string 8);; shell test;; print test;; print_int !nswaps;;