let split l = 
    let rec aux l n acc = match l with
    | [] -> [], []
    | h::t when n=0 -> (List.rev acc, h::t)
    | h::t -> aux t (n-1) (h::acc)
    in aux l (List.length l / 2) [];;

let merge l1 l2 = 
    let rec aux l1 l2 _acc = match l1, l2 with
    | [], _ -> l2
    | _, [] -> l1
    | h1::t1, h2::t2 -> if h1 < h2
        then h1::(aux t1 l2 _acc)
        else h2::(aux l1 t2 (_acc + List.length l1))
    in aux l1 l2 0;;