home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / Caml Light 0.61 / Source / src / lib / sort.ml < prev    next >
Encoding:
Text File  |  1993-09-24  |  634 b   |  26 lines  |  [TEXT/MPS ]
  1. (* Merging and sorting *)
  2.  
  3. let merge order =
  4.   merge_rec where rec merge_rec = fun
  5.     [] l2 -> l2
  6.   | l1 [] -> l1
  7.   | (h1::t1 as l1) (h2::t2 as l2) ->
  8.       if order h1 h2 then h1 :: merge_rec t1 l2 else h2 :: merge_rec l1 t2
  9. ;;
  10.  
  11. let sort order l =
  12.   let rec initlist = function
  13.       [] -> []
  14.     | [e] -> [[e]]
  15.     | e1::e2::rest ->
  16.         (if order e1 e2 then [e1;e2] else [e2;e1]) :: initlist rest in
  17.   let rec merge2 = function
  18.       l1::l2::rest -> merge order l1 l2 :: merge2 rest
  19.     | x -> x in
  20.   let rec mergeall = function
  21.       [] -> []
  22.     | [l] -> l
  23.     | llist -> mergeall (merge2 llist) in
  24.   mergeall(initlist l)
  25. ;;
  26.