DO NOT COPY - PASTE.

Using F# language. Full and complete answers in order to get full credit please.Thank you.

Here is an attempt to write mergesortin F#:

 let rec merge = function | ([], ys) -> ys | (xs, []) -> xs | (x::xs, y::ys) -> if x < y then x :: merge (xs, y::ys) else y :: merge (x::xs, ys) let rec split = function | [] -> ([], []) | [a] -> ([a], []) | a::b::cs -> let (M,N) = split cs (a::M, b::N) let rec mergesort = function | [] -> [] | L -> let (M, N) = split L merge (mergesort M, mergesort N) 

Analyze mergesort with respect to the Checklist for Programming with Recursion, again addressing all three Steps. (Assume that merge and split both work correctly, as indeed they do.)

Enter this program into F# and see what type F# infers for mergesort. Why is this type a clue that something is wrong with mergesort?

Based on your analysis, correct the bug in mergesort.