let rec insert ineq a = fun
        | [] -> [a]
        | (b::q) when ineq a b -> a::b::q
        | (b::q) -> b::(insert ineq a q)
;;

let insert_c = insert (prefix <) ;;
let insert_d = insert (prefix >) ;;

let rec merge ineq = fun
        | [] l -> l
        | l [] -> l
        | (a::q) (b::r) when ineq a b -> a::(merge ineq q (b::r))
        | l (b::r) -> b::(merge ineq l r)
;;

let merge_c = merge (prefix <) ;;
let merge_d = merge (prefix >) ;;

let rec sort ineq l =
        let rec coupe p = fun
                | [] -> [],[]
                | (a::q) -> let u,v = coupe p q in
                            if ineq a p then (a::u),v else u,(a::v)
        in
        match l with
                |  [] -> []
                | [a] -> [a]
                | (a::q) -> let u,v = coupe a q in
                            let uu = sort ineq u and vv = sort ineq v in
                            uu@(a::vv)
;;

let sort_c = sort (prefix <) ;;
let sort_d = sort (prefix >) ;;