$2.(20$ points$)$ Here is an SML mergesort program:

$```$

fun merge$([],$ ys$)=$ ys

$|$ merge$($xs$,[])=$ xs

$|$ merge$($x::xs$,$ y::ys$)=$

if x $$ y then x::merge$($xs$,$ y::ys$)$

else y::merge$($x::xs$,$ ys$)$

fun split $[]=([],[])$

$|$ split $[$a$]=([$a$],[])$

$|$ split $($a::b::cs$)=$

let val $($M$,$N$)=$ split cs in

$($a::M$,$ b::N$)$

end

fun mergesort $[]=[]$

$|$ mergesort $[$a$]=[$a$]$

$|$ mergesort $[$a$,$b$]=$ if a b then $[$a$,$b$]$ else $[$b$,$a$]$

$|$ mergesort L $=$

let val $($M$,$N$)=$ split L

in

merge $($mergesort M$,$ mergesort N$)$

end

$```$ Note that mergesort includes three base cases $([]\backslash (,[$a$],[$a$,$ b$]\backslash ))$ and all are handled correctly.

Suppose we delete the third line of mergesort, so that $\backslash ([$a$,$ b$]\backslash )$ is no longer handled as a base case. You can verify that this change makes no difference in the type of mergesort or in its behavior.

Now suppose we also delete the second line of mergesort, leaving

$```$

fun mergesort $[]=[]$

$|$ mergesort L $=$

let val $($M$,$N$)=$ split L

in

merge $($mergesort M$,$ mergesort N$)$

end

$```$

What effect does this change have on the type that SML infers for mergesort?

Verify that whether updated mergesort works correctly by running on your system and explain your findings.