マージソート書いてみた
ソース↓
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"]