Merge Sort Program

Question

I have written the following program to implement merge sort in F#.

Can you please review this and let me know how can I write this in the most functional way (also most efficient and concise)?

In my recursion call, mergeSort is called again twice. I think it will be great if these two calls could be made on different threads.

Do I have to explicitly create separate threads or will F# automatically detect and execute on different cores (threads)? I have heard that functional languages are more multi-core friendly so I wonder what sort of optimization will be done by F# (or perhaps if this code was written in Haskell or pure functional language).

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"
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
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
[<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

Answer 1

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.