(* insertion sorting via binary search trees *)
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)
let rec flatten tr =
match tr with
Leaf -> []
| Node(x, tr1, tr2) -> flatten tr1 @ [x] @ flatten tr2
let sort xs = flatten(insertList xs Leaf)
(* try: sort [3;1;2;5;3];; *)