home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Tools / Languages / MacGofer 0.22d / MacGofer 0.22d Release / Gofer Demos / FastSort < prev    next >
Encoding:
Text File  |  1993-06-01  |  1.5 KB  |  14 lines  |  [TEXT/GFER]
  1. {- list sorting: see L.C.Paulson, ML for the working programmer, Cambidge, p100
  2. -- The list is split into ascending chunks which are then merged in pairs.
  3.  
  4. samsort l = sorting [] 0 l
  5.   where    sorting ls k []        = head(mergepairs ls 0)
  6.     sorting    ls k (x:xs)    = sorting (mergepairs (run:ls) kinc) kinc tl
  7.       where    (run, tl)    = nextrun [x] xs
  8.         kinc        = k+1
  9.     nextrun run []        = (reverse run, [])
  10.     nextrun    rs@(r:_) xl@(x:xs)
  11.         | x<r        = (reverse rs, xl)
  12.         | otherwise    = nextrun (x:rs) xs
  13.     mergepairs [l] _ = [l]
  14.     mergepairs l