Module Insertion
A functional implementation of insertion sort. The sorting proceeds
in reverse direction of the list.
module InsertionsortFun (E: ORDERED) : (SORT with type elem = E.t) =
struct
type elem = E.t
let rec sort (l: elem list) =
let rec i_one (x: elem) (l': elem list) = (* insert x at the right place *)
match l' with
[ ] ® [x]
| y::l'' ®
if (x £ y) then x::l' else y:: (i_one x l'')
in match l with
[ ] ® [ ]
| x:: l' ® i_one x (sort l')
end
January 31, 2002