A simple sort result checker used to test the correctness of sorting function in a black box setting. This is taken from http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.112.3042&rep=rep1&type=pdf .

sort_check.ml

let x = [1;3;4;5;1;2;10;7];; 
let y = List.sort compare x;;


let convert_pos list n =
let rec aux i r = function
| [] -> r
| e::t -> aux (i+1) (r @ [e*n+i]) t
in aux 0 [] list;;

let x' = convert_pos x 8;;

let y' = List.sort compare x';;

let verify_pos list_y' list_x' n = 
let rec aux2  = function
| [] -> Some true
| e::t -> 
if List.nth list_x' (e mod n) != e then
None
else 
aux2 t 
in aux2 list_y' ;;

let g = verify_2 y' x' 8;;

let div_list list n = 
List.map (fun a -> a / n) list ;;

let y'' = div_list y' 8;;

let verify_sorted list = 
let rec all_less = function 
| [] -> Some true
| f::s::r -> 
if f < s then
all_less r
else
None
in all_less list ;;

let r = is_sorted y';;
let u = is_sorted x;;

let verify_length list n =
if List.length list = n then
Some true
else
None
;;

let cl = is_correct_length y' 8;;
let t = y = y'';;