(*
 * InsertSort
 *
 * This function sorts a sequence of numbers or strings into ascending order
 * using insertion sort.
 *
 * Examples:
 *
 *      <3 1 4 1 5 9 2> : InsertSort == <1 1 2 3 4 5 9>
 *
 *      <all work and no play> : InsertSort == <all and no play work>
 *
 * The sequence may not mix strings and numbers.
 *)
DEF InsertSort AS
   IF null THEN id			(* Check for trivial case *)
   ELSE
      [tl,[1]] | apndr | 
      INSERT
	 {[Element,Seq] := id}
         {[Left,Right] := [Seq, distl | FILTER > END | length] | [takel,dropl]}
	 [Left,[Element],Right] | cat
      END
   END;

