(* This is McCarthy's version of von Neumann's sort, compacted: *)
(* It is n log n for worst case. *)
(* Almost the same as List.sort *)
(* List.sort uses log(n) stack space.
This uses n stack space. *)
let sort less lst =
let rec fp l = match l with
[] -> []
| [a] -> [[a]]
| a::b::c -> (if less a b then [a; b] else [b; a])::(fp c)
in let rec mrg a b = match (a, b) with
| (c, []) -> a
| ([], c) -> b
| (c::d, e::f) -> if less c e then c::(mrg d b) else e::(mrg f a)
in let rec lmrg llst = match llst with
[] -> []
| [a] -> [a]
| a::b::c -> (mrg a b)::(lmrg c)
in let rec rlm lx = match lx with
| [] -> []
| [a] -> a
| a::b::c -> rlm (lmrg lx)
in rlm (fp lst);;
(* test of sort:
open Random;;
let rec bl n = if n = 0 then [] else (bits ())::(bl (n - 1));;
let rec sum l = match l with [] -> 0 | a::b -> a + (sum b);;
let ls = bl 10000;;
sum ls;;
let lss = sort (<) ls;;
sum lss;;
let rec tv ls = match ls with [] -> true | [a] -> true
| a::b::c -> a <= b && tv (b::c);;
tv ls;; (* false *)
tv lss;; (* true *)
let ls2 = List.sort (-) ls;;
lss = ls2;; (* true *) *)
(* On Mac OSX, with the bash shell, you can give the command
ulimit -s hard
whereupon you can sort about 100000 integers instead of 10000. *)