mergesort.fsx

module Extensions = 
    type System.Collections.Generic.List<'a> with
        member this.Split (first: int, last: int) = 
            let count = (last - first) + 1
            let result = this.GetRange(first, count)
            result


module Algorithms = 
    open Extensions
    let binary_search list value =
        let rec impl(list: 'a list) (value :'a) (hi: int) (low:int)  =
            let index = (hi + low) / 2
            match compare value (list.Item(index)) with
            | 0  -> Some(index)
            | 1 -> impl list value hi index
            | -1 ->  impl list value index low
            | _ -> None
        match list with
        | [] -> None
        | _ -> impl list value (List.length list) 0

    let merge_sort<'a when 'a : comparison> (l: System.Collections.Generic.List<'a>) =
       
        let rec merge (a: System.Collections.Generic.List<'a>) (b: System.Collections.Generic.List<'a>)  (c: System.Collections.Generic.List<'a>)=
            if a.Count = 0 then
                c.AddRange b
                c
            elif b.Count = 0 then 
                c.AddRange a
                c
            else
                match compare (a.Item 0) (b.Item 0) with
                    | 0 -> 
                        c.Add (a.Item 0)
                        merge (a.Split(1,a.Count - 1)) b c
                    | -1 -> 
                        c.Add (a.Item 0)
                        merge (a.Split(1,a.Count - 1)) b c
                    | 1 -> 
                        c.Add (b.Item 0)
                        merge a (b.Split(1,b.Count - 1)) c


        let rec merge_sort_impl(s: System.Collections.Generic.List<'a>) = 
            if s.Count = 1 then
                s
            else
                let midpoint = s.Count / 2
                let first = s.Split(0, midpoint - 1) |> merge_sort_impl
                let last = s.Split(midpoint , s.Count - 1) |> merge_sort_impl
                merge first last (new System.Collections.Generic.List<'a>())
        if l = null || l.Count = 0 then
            System.Collections.Generic.List<'a>()
        else
        merge_sort_impl l