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