Created
January 29, 2012 13:23
-
-
Save komamitsu/1698799 to your computer and use it in GitHub Desktop.
OCaml merge sort
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
let split_rev cut xs = | |
let (_, f, s) = | |
List.fold_left | |
(fun (i, f, s) x -> | |
if i < cut then (i + 1, x::f, s) else (i + 1, f, x::s)) | |
(0, [], []) xs | |
in | |
(f, s) | |
let rec ms xs = | |
let len = List.length xs in | |
if len <= 1 then xs | |
else begin | |
let (l, r) = split_rev (len / 2) xs in | |
let (l, r) = (ms l, ms r) in | |
let rec merge a l r = | |
match (l, r) with | |
| (l, []) -> List.rev a @ l | |
| ([], r) -> List.rev a @ r | |
| (lhd::ltl, rhd::rtl) when lhd < rhd -> merge (lhd::a) ltl r | |
| (lhd::ltl, rhd::rtl) -> merge (rhd::a) l rtl | |
in | |
merge [] l r | |
end | |
let _ = | |
Random.self_init (); | |
let n = 400 in | |
let xs = | |
let rec loop i xs = | |
if i >= n then xs else loop (i + 1) (Random.int n::xs) | |
in | |
loop 0 [] in | |
let p xs = | |
List.iter (fun x -> print_int x; | |
print_string " ") xs; | |
print_newline () | |
in | |
print_endline "=== original values ==="; | |
p xs; | |
print_endline "=== sorted values ==="; | |
p (ms xs) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment