fun insertionsort(lis) = 
	if lis = nil then []
	else 
		insert(hd(lis), insertionsort(tl(lis)));

fun insert(element, lis) =
	if lis = nil then [element]
	else if element>hd(lis) then
		[hd(lis)] @ insert(element, tl(lis))
	else
		[element] @ lis;

fun insertionsort2(nil) = []
| 	insertionsort2(first::rest) =
		insert2(first, insertionsort2(rest));
		
fun insert2(element, nil) = [element]
|	insert2(element,first::rest) =
		if element > first then
			[first] @ insert2(element, rest)
		else [element] @ first::rest;
(* 
- use "insertion.sml";
[opening insertion.sml]
- insertionsort([45,2,7,8,1,23,18]);
val it = [1,2,7,8,18,23,45] : int list
- insertionsort2([45,2,7,8,1,23,18]);
val it = [1,2,7,8,18,23,45] : int list

- insert(4,[5,6,7]);
val it = [4,5,6,7] : int list
- insert(4,[1,6,7]);
val it = [1,4,6,7] : int list
- insert(4,[1,2,7]);
val it = [1,2,4,7] : int list
- insert(4,[1,2,3]);
val it = [1,2,3,4] : int list

- insert2(4,[5,6,7]);
val it = [4,5,6,7] : int list
- insert2(4,[1,2,3]);
val it = [1,2,3,4] : int list
-
*)

NOT YET IMPLEMENTED IN ML

def flatten(lis)
	if lis.length == 0 then
		[]
	elsif lis[0].class != Array then
		[lis[0]] + flatten(lis[1..lis.length-1])
	else
		return flatten(lis[0]) + flatten(lis[1..lis.length-1])
	end
end

			
y = [5, 2, [16, [20, 1]], 30, [[[2]]]]
print flatten(y), "\n"

fun part(lis: int list, pivot):int list * int * int list =
	if lis = nil then
		([], pivot, [])
	else
		let 
			val r = part(tl(lis), pivot)    
					 (*recursive call which will
					   return a list with structure
					   ( (<= pivot) pivot (> pivot))
					  *)
		in 
			if hd(lis) > pivot then  (*  add to > list *)
			     (#1(r), pivot, hd(lis)::(#3(r)))
			     (* [ [hd(lis)]:: hd(tl(tl(r[2]))) ]  *)
			else  (* add to <= list *)
				(hd(lis)::(#1(r)),#2(r), #3(r))
		end;

fun partition(lis:int list) =
	part(tl(lis), hd(lis)); (* ((<= part) part (> part)) will be returned *)

(*
-  use "quicksort.sml";
val part = fn : int list * int -> int list * int * int list
val partition = fn : int list -> int list * int * int list
val it = () : unit
- partition([1,3,5,7,9,10]);
val it = ([],1,[3,5,7,9,10]) : int list * int * int list
- partition([10,45,8,1,9,15,20]);
val it = ([8,1,9],10,[45,15,20]) : int list * int * int list
*)