let divide_t l = match l with
    []->([],[])
    |h::t -> let rec aux l acc l1 l2 = match l with
        []->(List.rev(l2), List.rev(l1))
        |h::t -> if (acc mod 2) == 0 then aux t (acc+1) (h::l1) l2
                 else aux t (acc+1) l1 (h::l2)
    in aux l 1 [] [];;

let merge_t l1 l2 = match l1, l2 with
    ([],[])->[]
    |([], h::t) -> l2
    |(h::t, []) -> l1
    |(h::t, h1::t1)-> let rec aux l1 l2 l3 = match l1, l2 with
        ([],[])-> List.rev(l3)
        |(_,[])-> List.rev(l3)@l1
        |([], _)-> List.rev(l3)@l2
        |(h::t, h1::t1) -> if h <= h1 then aux t l2 (h::l3)
                           else aux t1 l1 (h1::l3)
    in aux l1 l2 [];;

let rec msort l = match l with
    [] | [_] -> l
    | _ -> let l1,l2 = divide l in
           merge (msort l1) (msort l2);;