[back]

Sorting by Flattening

type 'a tree
  = Empty
  | Node of 'a * 'a tree * 'a tree

Using insert and flatten, implement the function

val sort : 'a list -> 'a list

so that sort l is the elements of l in sorted order.

let _ = assert (sort [5; 3; 8; 1; 4] = [1; 3; 4; 5; 8])