(* insertion sorting via binary search trees with more efficient flattening *)
type 'a tree = Leaf
| Node of 'a * 'a tree * 'a tree
let rec insert x tr =
match tr with
Leaf -> Node(x, Leaf, Leaf)
| Node(y, tr1, tr2) ->
match compare x y with
-1 -> Node(y, insert x tr1, tr2)
| 0 -> tr
| _ -> Node(y, tr1, insert x tr2)
let rec insertList xs tr =
match xs with
[] -> tr
| x :: xs -> insertList xs (insert x tr)
(* optimal in terms of ::'s *)
let rec flattenOnto tr xs =
match tr with
Leaf -> xs
| Node(x, tr1, tr2) ->
flattenOnto tr1 (x :: flattenOnto tr2 xs)
let flatten tr = flattenOnto tr []
let sort xs = flatten(insertList xs Leaf)
(* try: sort [3;1;2;5;3];; *)