fun merge(l1,l2)=
if l1=nil then l2
else if l2=nil then l1
else if hd(l1) < hd(l2) then hd(l1)::merge(tl(l1),l2)
else hd(l2)::merge(l1,tl(l2));  

fun split_iter(l,i,l1,l2)=if l=nil then (l1,l2) else
if (i mod 2)=0 then split_iter(tl(l),i+1,l1,hd(l)::l2)
else split_iter(tl(l),i+1,hd(l)::l1,l2);    

fun split(l)=split_iter(l,1,[],[]);   

fun mergesort(l)=
if tl(l)=nil then [hd(l)] else
merge(mergesort(#1(split(l))),mergesort(#2(split(l))));