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

SCM Repository

[smlnj] Annotation of /MLRISC/releases/release-110.84/library/sorting2.sml
ViewVC logotype

Annotation of /MLRISC/releases/release-110.84/library/sorting2.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4728 - (view) (download)

1 : monnier 409 (*
2 :     * Newer merge sort. Stolen from a NJPLS meeting.
3 :     *
4 :     * -- Allen
5 :     *)
6 :    
7 :     signature SORTING =
8 :     sig
9 :    
10 :     val sort : ('a * 'a -> bool) -> 'a list -> 'a list
11 :     val uniq : ('a * 'a -> bool) -> 'a list -> 'a list
12 :     val sort_uniq : ('a * 'a -> bool) ->
13 :     ('a * 'a -> bool) -> 'a list -> 'a list
14 :    
15 :     end
16 :    
17 :     structure Sorting : SORTING =
18 :     struct
19 :    
20 :     infix ==
21 :    
22 :     val SOME maxInt = Int.maxInt
23 :    
24 :     fun sort op< =
25 :     let fun getRun [] = (0,[])
26 :     | getRun (h::t) =
27 :     let fun loop(last,n,[]) = (n,[])
28 :     | loop(last,n,l as h::t) =
29 :     if h < last then (n,l) else loop(h,n+1,t)
30 :     in loop(h,1,t) end
31 :     fun head([],_) = []
32 :     | head(_,0) = []
33 :     | head(h::t,n) = h::head(t,n-1)
34 :     fun merge(a,alen,b,blen) =
35 :     let fun loop([],_,b,blen) = head(b,blen)
36 :     | loop(_,0,b,blen) = head(b,blen)
37 :     | loop(a,alen,[],_) = head(a,alen)
38 :     | loop(a,alen,_,0) = head(a,alen)
39 :     | loop(a as ah::at,alen,b as bh::bt,blen) =
40 :     if ah < bh then ah::loop(at,alen-1,b,blen)
41 :     else bh::loop(a,alen,bt,blen-1)
42 :     in loop(a,alen,b,blen) end
43 :     fun iter(sorted,slen,[],want) = (sorted,slen,[])
44 :     | iter(sorted,slen,unsorted,want) =
45 :     if slen >= want then (sorted,slen,unsorted)
46 :     else
47 :     let val (runlen,runtail) = getRun unsorted
48 :     val (sorted',slen',unsorted) =
49 :     if runlen >= slen then
50 :     (unsorted,runlen,runtail)
51 :     else
52 :     iter(unsorted,runlen,runtail,runlen)
53 :     in iter(merge(sorted,slen,sorted',slen'),
54 :     slen+slen',unsorted,want)
55 :     end
56 :     fun main list =
57 :     let val (sorted,_,_) = iter([],0,list,maxInt)
58 :     in sorted end
59 :     in main end
60 :    
61 :     fun uniq op== =
62 :     let fun f [] = []
63 :     | f (l as [x]) = l
64 :     | f (x::(l as (y::z))) = if x == y then f l else x::f l
65 :     in f
66 :     end
67 :    
68 :     fun sort_uniq op< op== l = uniq op== (sort op< l)
69 :    
70 :     end

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0