Previous Contents Next

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 (EORDERED) : (SORT with type elem = E.t) =
   struct
     type elem = E.t
     let rec explode (la list) : ' a list list = 
       match l with 
         [ ] ® [ ]
       | x::tl ® [x] :: explode tl

     let rec merge_list (l1a list) (l2a list) = (* merge to sorted lists *)
       match (l1l2with
         ([ ], 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 (la 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
January 31, 2002
Previous Contents Next