let fitInPlace (list, element) =
    let rec fit(list, element, accum1) =
        match list with
        | [] -> accum1 @ [element]
        | h::t when element <= h -> accum1 @ (element :: list)
        | h::t -> fit(t, element, accum1 @[h])
    in fit(list, element, []);;

let sort list =
    let rec sortRec (list, result) =
      match (list, result) with
        | ([], _) -> result
        | (h1::t1, _) -> sortRec(t1, fitInPlace(result, h1))
    in sortRec(list, []);;

let zipListsAndSort(list1, list2) =
    let rec zip(list1, list2, res) =
        match (list1, list2) with
        | ([], []) -> sort res
        | ([], _) -> sort (res @ list2)
        | (_, []) -> sort (res @ list1)
        | (h1::t1, h2::t2) -> zip(t1, t2, [h1;h2] @ res)
    in zip(list1, list2, []);;

zipListsAndSort([1;2;3;4], [2;2;2;8]);;
zipListsAndSort([], [2;8;2;4]);;
zipListsAndSort([2;8;2;4], []);;
zipListsAndSort([5;4;3;2], [1;2;3;4;5;6]);;