(*let rec rlist r n =
    if n < 1
    then []
    else Random.int r :: rlist r (n-1)
;;*)

let r_list_r r n =
    let rec aux c a =
        if c = 0
        then a
        else aux (c-1) (List.rev_append [Random.int r] a)
    in
        if n < 1
        then []
        else aux n []
;;

(*let rec divide = function
    | h1::h2::t ->
        let t1, t2 =
            divide t
        in
            h1::t1, h2::t2
    | l-> l, []
;;

let rec merge ord (l1, l2) = match l1, l2 with
    | [], l
    | l, [] -> l
    | h1::t1, h2::t2 ->
        if ord h1 h2
        then h1::merge ord (t1,l2)
        else h2::merge ord (l1, t2)
;;*)

let rec m_sort c = function
    | [] -> []
    | [_] as temp -> temp
    | l ->
        let l1, l2 =
            divide l
        in merge c (m_sort c l1, m_sort c l2)
;;

(*m_sort (>) [8;9;5;6;7;4;1;3;2;0];;*)


let divide l =
    let rec aux (e, d) = function
        | [] -> List.rev e, List.rev d
        | h1::h2::t -> aux ( h1::e, h2::d ) t
        | l-> aux ( List.rev_append (List.rev l) e, d ) []
    in aux ([],[]) l;
;;

let merge_t f (l1, l2) =
    let rec aux (e, d, a) = match e, d with
        | [], [] -> List.rev a
        | [], l
        | l, [] -> List.rev_append a l
        | h1::t1, h2::t2 ->
            if f h1 h2
            then aux ( t1, d, h1::a )
            else aux ( e, t2, h2::a )
    in aux (l1, l2, [])
;;
merge_t (>) ( [8;1;6], [2;1;7] );;
(*
    merge_t (>) ( [8;1;6], [2;1;7] );;
    - : int list = [8; 2; 1; 7; 1; 6

*)

let rec m_sort2 c = function
    | [] -> []
    | [_] as temp -> temp
    | l ->
        let l1, l2 =
            divide_t l
        in merge_t c (m_sort2 c l1, m_sort2 c l2)
;;