Module Mergesort
A functional implementation of merge sort. The functional implementation
is a bit clumsy, since splitting the sequence is not
well-supported by lists. In the implementation, this is dealt with by
not splitting the list in the outer working of the divide-and-conquer
strategy, but to split the list in a pre-processing step into a list of
it's the basic one-element sublists (function explode),
which are then merged pairwise. The basic conquer-step, the merging of
two sorted lists into a larger, sorted one is done by
merge_list.
The implementation is a bit clumsy, since it hides the
divide-and-conquer structure of the algorithm.
module MergesortFun (E: ORDERED) : (SORT with type elem = E.t) =
struct
type elem = E.t
let rec explode (l: a list) : ' a list list =
match l with
[ ] ® [ ]
| x::tl ® [x] :: explode tl
let rec merge_list (l1: a list) (l2: a list) = (* merge to sorted lists *)
match (l1, l2) with
([ ], l2) ® l2
| (l1, [ ]) ® l1
| (x1::l1', x2::l2') ®
if x1 < x2 then x1 :: merge_list l1' l2
else x2 :: merge_list l1 l2'
let rec merge (l : a list list) =
let rec merge_step (l: a list list) : a list list =
(* Take the elements (= lists) in pairs of twos and merge them pairwise. *)
(* So, the function approcimately cuts the length of l in half. *)
match l with
[ ] ® [ ]
| [sl] ® [sl]
| l1 :: l2 :: rl ® merge_list l1 l2 :: (merge_step rl)
in
match l with
[ ] ® [ ]
| [sl] ® sl
| _ ® merge (merge_step l) (* start once again *)
let sort (l :elem list) = merge (explode l)
end
Pages last (re-)generated October 28, 2002 (Martin Steffen)