マージソート書いてみた

ソース↓

let rec mergesort cmp l =
    let rec merge l1 l2 res =
        match (l1, l2) with
        ([], []) -> res
        | ([], l) | (l, []) -> (List.rev l) @ res
        | (m::ms, n::ns) ->
            if (cmp m n) < 1 then merge ms l2 (m::res)
            else merge l1 ns (n::res)
    in
    let split l n =
        let rec split' l left c =
            match (l, c) with
            (x::xs, c) ->
                if c < n then split' xs (x :: left) (c+1)
                else (List.rev left, x::xs)
            | _ -> failwith "invalid list"
        in split' l [] 0
    in
    match l with
    [] | [_] -> l
    | _ ->
        let m = List.length l / 2 in
        let left, right = split l m in
        merge (mergesort cmp left) (mergesort cmp right) [] |> List.rev

↑の動作確認↓

let t = [2;7;1;8;2;8;1;8;2;8;4;5;9;0;4;1]
mergesort (fun x y -> compare x y) t
mergesort (fun x y -> compare y x) t

let s = ["Sapporo"; "Sendai"; "Tokyo"; "Yokohama"; "Aichi"; "Kyoto"; "Kobe"; "Fukuoka"; "Naha"]
mergesort (fun (x:string) (y:string) -> compare x.Length y.Length ) s

↑の結果↓

[0; 1; 1; 1; 2; 2; 2; 4; 4; 5; 7; 8; 8; 8; 8; 9]
[9; 8; 8; 8; 8; 7; 5; 4; 4; 2; 2; 2; 1; 1; 1; 0]
["Kobe"; "Naha"; "Tokyo"; "Aichi"; "Kyoto"; "Sendai"; "Sapporo"; "Fukuoka"; "Yokohama"]