(*sort*)

fun insert p e [] = [e]
   |insert p e (a::x)  = if p e a then e::a::x else a::insert p e x;
(* Given a binary predicate p, a sorted list and an element e,
   deliver the new list that has e inserted in order *)

fun beforep x y = x-y<0;
(* Is x less than y? *)

fun insert_sort p x = let fun sort p x [] = x
                             |sort p x (e::y) = sort p (insert p e x) y
                      in sort p [] x end;
(* Given binary predicate p and a list x, sort the list such that
   p a b holds, where x = (a::b::y). 
   The function "sort" takes as arguments binary predicate p,
   a sorted list x and a list y. It inserts the elements, e, of y
   into x. If y is nil, [], then the result is x, otherwise when
   the unsorted list is (e::y) the result is "sort p (insert p e x) y" *)

fun merge p [] [] = []
   |merge p (a::x) [] = (a::x)
   |merge p [] (b::y) = (b::y)
   |merge p (a::x) (b::y) = if p a b 
                            then a::merge p x (b::y)
                            else b::merge p (a::x) y;
(* Given binary predicate p and two sorted lists, x and y, merge these
   two list together. *)

fun firstn n [] = []
   |firstn 0 x = []
   |firstn n (a::x) = a::firstn (n-1) x;
(* Given a list x, deliver the first n elements of that list *)

fun skip 0 x = x
   |skip n [] = []
   |skip n (a::x) = skip (n-1) x;
(* Skip over the first n elements of a list, delivering the
   remaining list *)

fun lastn n x = skip ((length x) - n) x;
(* Give me the last n elements of a list. That is,
   if the list x if of size m, skip (n-m) x *)

fun merge_sort p [] = []
   |merge_sort p (a::nil) = [a]
   |merge_sort p (a::b::nil) = if p a b 
                               then a::b::nil
                               else b::a::nil
   |merge_sort p x = let val l = length x
                         val l1 = l div 2
                         val l2 = l - l1
                     in merge p (merge_sort p (firstn l1 x)) 
                                (merge_sort p (lastn l2 x)) end;
(* A merge sort. Given a list x of length l, merge together the merge_sort
   of the first l/2 elements with the last l/2 elements. *)

val x = insert_sort beforep [1,8,9,2,3,0,6];
val y = merge_sort beforep [1,8,9,2,3,0,6];

(* Use both sort functions to sort lists of arbitary objects *)