Home My Page Projects Code Snippets Project Openings SML/NJ
 Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

# SCM Repository

[smlnj] View of /sml/trunk/src/MLRISC/library/sorting2.sml
 [smlnj] / sml / trunk / src / MLRISC / library / sorting2.sml

# View of /sml/trunk/src/MLRISC/library/sorting2.sml

Thu Jun 1 18:34:03 2000 UTC (19 years, 3 months ago) by monnier
File size: 2104 byte(s)
```bring revisions from the vendor branch to the trunk
```
```(*
* Newer merge sort.  Stolen from a NJPLS meeting.
*
* -- Allen
*)

signature SORTING =
sig

val sort        : ('a * 'a -> bool) -> 'a list -> 'a list
val uniq        : ('a * 'a -> bool) -> 'a list -> 'a list
val sort_uniq   : ('a * 'a -> bool) ->
('a * 'a -> bool) -> 'a list -> 'a list

end

structure Sorting : SORTING =
struct

infix ==

val SOME maxInt = Int.maxInt

fun sort op< =
let fun getRun [] = (0,[])
| getRun (h::t) =
let fun loop(last,n,[])   = (n,[])
| loop(last,n,l as h::t) =
if h < last then (n,l) else loop(h,n+1,t)
in  loop(h,1,t) end
fun merge(a,alen,b,blen) =
| loop(a as ah::at,alen,b as bh::bt,blen) =
if ah < bh then ah::loop(at,alen-1,b,blen)
else bh::loop(a,alen,bt,blen-1)
in  loop(a,alen,b,blen) end
fun iter(sorted,slen,[],want) = (sorted,slen,[])
| iter(sorted,slen,unsorted,want) =
if slen >= want then (sorted,slen,unsorted)
else
let val (runlen,runtail) = getRun unsorted
val (sorted',slen',unsorted) =
if runlen >= slen then
(unsorted,runlen,runtail)
else
iter(unsorted,runlen,runtail,runlen)
in  iter(merge(sorted,slen,sorted',slen'),
slen+slen',unsorted,want)
end
fun main list =
let val (sorted,_,_) = iter([],0,list,maxInt)
in  sorted end
in  main end

fun uniq op== =
let fun f []                 = []
| f (l as [x])         = l
| f (x::(l as (y::z))) = if x == y then f l else x::f l
in  f
end

fun sort_uniq op< op== l = uniq op== (sort op< l)

end
```