(* An Ocaml program *) (* This is McCarthy's version of von Neumann's sort. *) (* Merge two sorted lists *) let rec mrg a b = match (a, b) with | (_, []) -> a | ([], _) -> b | (c::d, e::f) -> if c <= e then c::(mrg d b) else e::(mrg f a);; (* Merge list of sorted lists by adjacent pairs *) let rec lmrg llst = match llst with [] -> [] | [a] -> [a] | a::b::c -> (mrg a b)::(lmrg c);; (* Apply lmrg while there are more than 1 list *) let rec rlm lx = match lx with | [] -> [] | [a] -> a | a::b::c -> rlm (lmrg lx);; (* Make list into list of sorted pairs *) let rec fp l = match l with [] -> [] | [a] -> [[a]] | a::b::c -> (if (<=) a b then [a; b] else [b; a])::(fp c);; (* The sort proper *) let sort lq = rlm (fp lq);;