SML merge sort

merge.sml

datatype 'a tree = Empty | Node of {l:'a tree, x: 'a, r: 'a tree}
type 'a set = ('a * 'a -> bool) * 'a tree

(* Note to self: next time I think an AVL tree is a good idea,
    place head in microwave until the thought goes away... *)

fun makeBST cmp vs = let
	fun half ls = length ls div 2;
	fun mergesort [] = []
	|   mergesort [x] = [x]
	|   mergesort lst = let
		fun merge []      ys      = ys
		|   merge xs      []      = xs
		|   merge (x::xs) (y::ys) = 
			  if not (cmp(y, x) orelse cmp(x,y)) then (merge xs (y::ys))
			  else if cmp(x,y)                   then x::(merge xs (y::ys))
			  else                                    y::(merge (x::xs) ys);
	
	in
		merge (mergesort (List.take (lst, half lst)))
			  (mergesort (List.drop (lst, half lst)))
	end;
	fun split []  = Empty
	|   split [x] = Node{l=Empty,x=x,r=Empty}
	|   split xs  = let
		val left  = split (List.take(xs, half xs));
		val root  = hd (List.drop (xs, half xs));
		val right = split (List.drop(xs, half xs + 1));
	in
		Node{l=left,x=root,r=right}
	end;
in
	split (mergesort vs)
end;

fun searchBST cmp (Empty :'a tree) (v:'a) = false
  | searchBST cmp (Node{l,x,r}:'a tree) v = 
		if not (cmp(v, x) orelse cmp(x,v)) then true
		else if cmp(v, x) then searchBST cmp l v
			 else              searchBST cmp r v;

fun makeSET comp l : 'a set = (comp, (makeBST comp l));
fun SETcontains (s: 'a set) (x: 'a) = searchBST (#1 s) (#2 s) x;

what is the [x]?

@quangogster

For some reason I don't get an email notification on gists....

the [x] represents an array consisting of a single value. In other words: how do you sort an array of only a single value? You just return it unchanged.