(* 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);;