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