F#: Recursive functions: Split a list into two equal parts
<p>I'm having some errors with split and mergesort. (Note this is a formatted assignment requiring specific input &amp; output types for each function)</p>

<p>Here is my code right now:</p>

<pre><code>(* val split : l:'a list -&gt; 'a list * 'a list *)
let split (l:'a list -&gt; 'a list * 'a list) = 
    let rec splitInner = function
        | [],[] -&gt; [],[]
        | x::xs, acc -&gt;
            if xs.Length&gt;(acc.Length) then splitInner (xs x::acc)
            else xs acc
    splitInner (l, acc)

error FS0001: This expression was expected to have type
    'a list * 'b list    
but here has type
    'c list

(* val merge : 'a list * 'a list -&gt; 'a list when 'a : comparison *)
let rec merge l = 
    match l with
    | (xs,[])-&gt;xs
    | ([],ys)-&gt;ys
    | (x::xs, y::yr) -&gt;
        if x&lt;=y then x::merge(xr,y::yr)
        else y::merge(x::xr,yr)

(* val mergesort : l:'a list -&gt; 'a list when 'a : comparison *)
let rec mergesort l = 
    match l with
    | [] -&gt; []
    | [x] -&gt; [x]
    | xs -&gt; let (ys,zs) = split xs then merge(mergesort ys, mergesort zs)
</code></pre>

<p>The acc function is not working with split and the "then" in the last line of code is not right. </p>

<p>The idea is as follows: the given list l is split into two equal (if the length of l is odd then one of the “halves” is one item longer than the other) lists l1 and l2. These lists are sorted recursively and then the results are merged back to give a single sorted list. Code this in F#. Your algorithm can use &lt; as a comparison operator. Your code must have a function split that produces a pair of lists, a function merge that merges sorted lists and a function mergesort that implements the overall algorithm.</p>

<p>EDIT: I believe I am not allowed to use <code>|&gt; List.splitAt</code> on this assignment. I am trying to implement a helper function which will do the same thing.</p>

<p>EDIT2: Thank you Guy Coder, your answers are very thorough. I need the function split to take in only a list. Perhaps I may create a helper function inside that uses index based upon <code>list.Length/2</code>? It is assumed that the list input is a <code>float list</code>, and the function returns 2 <code>float lists</code>.</p>

<p>EDIT3: I feel much closer: here is my split function and the error I receive.</p>

<pre><code>(* val split : l:'a list -&gt; 'a list * 'a list *)
let split l = 
    let rec splitInner l counter list1 list2 =
        match (l, counter) with
        | (x::xs,c) -&gt;
            if c &lt; (l.Length/2) then
                let list1 = x :: list1
                let counter = counter+1
                splitInner xs counter list1 list2
            else
                let list2 = x :: list2
                let counter = counter+1
                splitInner xs counter list1 list2
        | ([],_) -&gt; ((reverse list1), (reverse list2))
    splitInner (l 0 [] [])
split [1;2;3;4;5;6;7;8;9;10]

error FS0001: This expression was expected to have type
    int -&gt; 'a list -&gt; 'b list -&gt; 'c list    
but here has type
    'd list
</code></pre>