// Learn more about F# at http://fsharp.net
// See the 'F# Tutorial' project for more help.

let rec qsort1 = function
    | h::t ->
        (qsort1 (List.filter (fun x -> x <= h) t)) @ [h] @
        (qsort1 (List.filter (fun x -> x > h) t))
    | [] -> []

let rec qsort2 = function
    | h::t ->
        let l, r = (List.partition (fun x -> x <= h) t)
        (qsort2 l) @ [h] @ (qsort2 r)
    | [] -> []


let rec mergesort l =
    let rec merge a b out =
        match (a, b) with
        | ([], y) -> y::out
        | (x, []) -> x::out
        | (x::xs, y::ys) ->
            if x <= y then merge xs b (x::out)
            else merge a ys (y::out)

    let rec split l a1 a2 =
        match l with
        | [] -> (a1, a2)
        | [x] -> (a1 @ l, a2)
        | x::y::t -> split t (a1 @ [x]) (a2 @ [y])

    if List.length l < 2 then l
    else
        let l, r = split l [] []
        List.rev (merge (mergesort l) (mergesort r) [])




[<EntryPoint>]
let main argv =
    printfn "%A" (qsort1 [10..-1..0])
    printfn "%A" (qsort2 [10..-1..0])
    printfn "%A" (mergesort [10..-1..0])

    0 // return an integer exit code