Sorting Concatenation Lists

A concatenation list is a list whose constructors are based on concatenation instead of cons. It has a constructor for the empty list (Nil), a single element list (Single), and the concatenation of two lists (Concat).

type 'a concatlist
  = Nil
  | Single of 'a
  | Concat of 'a concatlist * 'a concatlist

Implement the function

val sort : 'a concatlist -> 'a list

so that sort l is a regular list with the same elements as l but in sorted order. You should do this without first converting l into a regular list; in particular, you cannot use the function List.sort.

let l = Concat (Concat (Single 3, Single 2), Concat (Single 1, Single 10))
let _ = assert (sort l = [1;2;3;10])