Pages

Saturday, September 29, 2012

F# on Algorithms - merge sort

Not every Saturday is a pleasant sunshine blue sky. Today is one of these Saturdays.

The real driving power for F# is business requirements from the community and the success of F# depends on the success of community. I was hoping these materials can  inspires discussions around F# and eventually increase the adoption of F#. Our team, like me, wants to serve the community better, so please tell me, your code has bug, your code can be more concise, or your code is shit. 

So please, together, we can make it.

open System

let rec merge list0 list1 = 
    match list0, list1 with 
    | [], [] -> []
    | [], list
    | list, [] -> list
    | h0::t0, h1::t1 -> 
        if h0 < h1 then
            [h0] @ merge t0 list1
        else
            [h1] @ merge list0 t1

let rec mergeSort list = 
    match list with
    | [] -> []
    | [a] -> [a]
    | [a; b] -> [ min a b; max a b ]
    | _ -> 
        let firstHalf = 
            list 
            | > Seq.take (list.Length / 2)
            | > Seq.toList
        let secondHalf = 
            list
            | > Seq.skip (list.Length / 2)
            | > Seq.toList

        let sortedFirstHalf = mergeSort firstHalf
        let sortedSecondHalf = mergeSort secondHalf

        merge sortedFirstHalf sortedSecondHalf

mergeSort [1;3;9;2;4;7;6;5]


No comments: