fun insertionsort op< =
let
fun insert x [] = [x]
| insert x (y::ys) = if x < y then x::y::ys else y::insert x ys
fun isort [] = []
| isort (x::xs) = insert x (isort xs)
in
isort
end
fun mergesort op< =
let
fun split [] ys zs = (ys,zs)
| split [z] ys zs = (ys,z::zs)
| split (y::z::xs) ys zs = split xs (y::ys) (z::zs)
fun merge [] ys = ys
| merge xs [] = xs
| merge (x::xs) (y::ys) = if x < y then x :: merge xs (y::ys)
else y :: merge (x::xs) ys
fun msort [] = []
| msort [x] = [x]
| msort xs = let val (ys,zs) = split xs [] [] in
merge (msort ys) (msort zs)
end
in
msort
end
fun quicksort op< =
let
fun qsort ys [] = ys
| qsort ys (p::xs) = part p xs ys [] []
and part p [] ys l r = qsort (p :: qsort ys r) l
| part p (x::xs) ys l r = if x < p then part p xs ys (x::l) r
else part p xs ys l (x::r)
in
qsort []
end