A good start if you want to see a functional approach to a problem would be looking up a Haskell implementation. Poor guys are doomed to do things the functional way, so we might just as well use that - here's a pretty in-depth description. It translates nicely to F# (minus one thing I'll talk about later).
So without further ado:
let take n list = List.ofSeq <| Seq.take n list let rec takeRest n list = match (n, list) with | (0, l) -> l | (n, _ :: tl) -> takeRest (n - 1) tl | (_, _) -> failwith "unknown pattern"
These are generally fine, however if you're already using Seq.take, there's also Seq.skip that does what your takeRest does, so you might use that.
It's not the ideal way to split a list - look into the linked Haskell implementation for more of that.
Also, going for a single split function is nicer in my opinion - let's say we have a function split: a' list -> (a' list * a' list) here. It can still use Seq.take/skip/length for now, can be switched for a better one transparently.
let rec mergeList list1 list2 = match (list1, list2) with | [], [] -> [] | [], l -> l | l, [] -> l | hd1 :: tl1, (hd2 :: _ as tl2) when hd1 < hd2 -> hd1 :: mergeList tl1 tl2 | l1, hd2 :: tl2 -> hd2 :: mergeList l1 tl2
Here, the first pattern is superfluous - the second and the third one cover the scenario already. The final two patterns seem clearer when you collapse them into a single one and move the when clause inside the pattern's body like this:
| x::xs, y::ys -> if x <= y then x :: (mergeList pred xs y::ys) else y :: (mergeList pred x::xs ys)
Also note the <= there, so the order of elements is preserved.
Your implementation however still has a problem that this doesn't fix - for large lists (around 100000 elements for me) you will get a StackOverflowException here, since the mergeList is not tail-recursive. In Haskell, a similar construct gives tail-recursive code due to optimization which F# doesn't have. You can make it tail-recursive in the usual way however, by using an accumulator instead of consing.
let rec mergeSort = function | [] -> [] | [x] -> [x] | l -> let n = (int)(List.length l / 2) let list1 = mergeSort (take n l) let list2 = mergeSort (takeRest n l) mergeList list1 list2
Assuming you have the split function defined as earlier, you can replace the third pattern's body like this:
let left, right = split l mergeList (mergeSort left) (mergeSort right)
Makes it more concise.
[<EntryPoint>] let main args = let input = [10; 7; 1; 0; -1; 9; 33; 12; 6; 2; 3; 33; 34;]; List.iter (fun x -> printfn "%i" x) (mergeSort input) 0
So yeah, the code has a problem with larger inputs, which you obviously didn't test ;) So as a bonus, a simple input generator I wrote for checking your code.
let generateInput rand min max len = Seq.unfold(fun (i, rand:Random) -> if i < len then Some <| (rand.Next(min, max), (i+1, rand)) else None) (0, rand) let input = generateInput (System.Random()) -1000 1000 10000 |> List.ofSeq
Edit:
As for the other part of your question - F# will not do anything to make the code run in parallel by itself. You'd have to tell it to do it yourself. This would typically involve using async workflows. Another option would be parallel collection functions from F# PowerPack like Seq.pmap or the regular .NET mechanisms for parallelism like tasks.
Anyway, asyncs are really cool if you have many long-running IO bound operations, but don't gain you much if all you're doing is sorting ints.
